Численные методы решения нелинейных уравнений

Размещено на http://www.allbest.ru/

Лекционный курс

Тема: Численные методы решения нелинейных уравнений (6 часов)

План

1. Решение нелинейных уравнений

2. Отделение корней нелинейного уравнения

3. Уточнение корней

4. Конечные методы уточнения корней

5. Итерационные методы уточнения корней

6. Методы решения систем нелинейных уравнений

Литература

1. Решение нелинейных уравнений

нелинейный уравнение дихотомия корень

Во многих научных и инженерных задачах возникает необходимость решения нелинейных уравнений вида: f(x)=0. Решение такого уравнения принято называть корнем. Решить уравнение с заданной погрешностью фактически означает указать значение корня такое, что в интервал неопределенности корня попадает и точка пересечения графика функции f(x) с осью х. Эта точка и есть точное значение корня.

Численное решение нелинейного уравнения обычно проводят в два этапа. На первом этапе необходимо отделить корни нелинейного уравнения, т.е. найти такие интервалы изменения переменной , где расположен только один корень. По сути дела, на этом этапе находят приближённое значение корней с погрешностью равной половине длины интервала (интервал неопределенности корня). Приближенное значение корня при этом выбирается в центре данного интервала. Нередко отделение корней удаётся провести, не обращаясь к математическим методам и алгоритмам, на основании физического смысла задачи или из анализа её упрощённой модели. На втором этапе проводят уточнение отделённых корней, т.е. находят корни с заданной точностью, для этого известен богатый набор алгоритмов, например, метод дихотомии рассмотренный ниже.

Вывод:

Процесс решения нелинейных уравнений разбивается на два этапа:

Отделение корней

Уточнение корней

2. Отделение корней нелинейного уравнения

Отделить корни - задать такие отрезки, на которых корень существует и он единственный. Основная проблема задачи отделения - возможность наличия нескольких (в принципе бесконечного количества) корней.

Рассмотрим два наиболее употребительных на практике метода отделения корней:

А) Графический метод.

Суть метода заключается в построении графика функции f(x) для нелинейного уравнения вида f(x)=0. На графике выделяются отрезки, на которых есть один единственный корень (точка пересечения функцией оси Х). При необходимости выяснить поведение функции строится график части отрезка в увеличенном масштабе.

Б) Приближенный аналитический метод.

Аналитический метод основан на теореме математического анализа - если непрерывная функция меняет знак на концах отрезка [a,b] (т.е. f(a)*f(b) < 0), то на этом отрезке обязательно существует корень уравнения f(x)=0. Используя теорему можно построить простой метод отделения корней на конечном отрезке- разделить весь отрезок на большое число маленьких отрезков и проанализировав произведение функции на концах отрезков f(ai)*f(bi) выделить отрезки, где это произведение отрицательно или равно нулю (корень в конце отрезка). К сожалению, существуют возможности поведения функции f(x), которые приведут в этом алгоритме к потере корней:

В приведенных примерах:

В первом случае функция не меняет знак, но корни есть - их четное количество 2,4,6 ….

Во втором случае функция меняет знак, но корней 3 а не один. Возможны так же варианты 5, 7, 9 и другого нечетного количества корней.

В принципе математика не дает общего метода отделения корней для любого нелинейного уравнения, хотя существует частные методы отделения корней некоторых классов функций f(x) - тригонометрические, полиномы. Однако для практического использования можно сформулировать не абсолютно точный, но достаточно эффективный метод, основанный на простейшем алгоритме.

Приведем такой примерный алгоритм отделения корней аналитически:

Задается отрезок [a,b], на котором необходимо отделить корни функции f(x).

Задается начальное значение n и строится сетка

,

.

Сетка делит отрезок на n частей с помощью n+1 точки.

Вычисляется значение функции f(xi)=fi и вычисляется произведение значений функции на концах отрезка , i = 0,1,2,…n+1.

Подсчитываем количество отрицательных произведений и запоминаем отрезки, где произведение отрицательно или равно 0. Число таких отрезков k. Каждый из таких отрезков должен содержать хотя бы 1 корень.

Увеличиваем n в два раза и повторяем процедуру. Получаем новое количество отрезков (корней) k1.

Если

Данный алгоритм теоретически может пропустить корень, но практика показала его эффективность и достаточную точность.

3. Уточнение корней

Методы уточнения корней делятся на конечные и итерационные. Конечные методы основаны на идее уменьшения интервала неопределенности на каждом шаге с помощью какого-либо процесса.

Суть итерационного метода в построении итерационной формулы и вычисления итерационной последовательности такой, чтобы эта последовательность сходилась к заданному корню.

Конечный метод построен таким образом, что можно заранее оценить количество итераций, которое потребуется для уточнения корня с заданной погрешностью. Для итерационного метода это не возможно. К конечным методам можно отнести метод «дихотомии» (деления отрезка пополам) и конечный вариант метода хорд.

нелинейный уравнение дихотомия корни

4. Конечные методы уточнения корней нелинейного уравнения

Метод дихотомии - деления отрезка пополам

Суть метода: Пусть задан отрезок [a,b] на котором отделен корень уравнения f(x)=0. Если разделить этот отрезок пополам точкой С, то можно проверить знак произведения F(a)*F(c) и выбрать ту часть отрезка, где это произведение отрицательно и находится корень. Таким образом, отрезок неопределенности корня уменьшится в 2 раза. Это 1 итерация метода. За n итераций отрезок уменьшится в 2n раз. Если необходимо получить результат с абсолютной погрешностью , то можно оценить количество итераций n

(b-a)/ 2n < => (b-a)/ < 2n => n > ln((b-a)/) / ln(2)

Алгоритм метода дихотомии:

Задаем уравнение F(x)=0, отрезок для корня [a,b], погрешность .

Ищем с=(a+b)/2 и значение произведения F(a)*F(c).

Если F(a)*F(c)<0 => a=a; b=c, при F(a)*F(c)>0 => a=c; b=b, при F(c)=0 a=b=c.

Находим оценку погрешности d=|b-c|. Если d> то возвращаемся в п.2, в противном случае найден корень Хк = с при заданной погрешности.

Метод хорд

Суть метода: Если в методе дихотомии выбор точки С изменить на точку пересечения хорды с осью х, то мы получим новый более быстрый конечный метод. Найдем значение точки С - пересечения хорды с осью х. Из правила подобия треугольников получаем 2 формулы вычисления:

или

Обе эти формулы должны давать один и тот же результат, но с точки зрения реализации итераций метода они отличаются кардинально.



Проблемой такого метода является тот факт, что как правило работает только одна из формул. Это значит, что один из концов отрезка всегда остается неподвижным. Можно легко определить какой именно - например на вышележащем рисунке хорда отделяет корень на отрезке [С,В], следовательно новая хорда вновь будет отсекать точку С слева от корня, хотя и гораздо ближе к нему. Таким образом, если мы будем оценивать отрезок неопределенности как [С,В], то это будет явно неправильно - длина этого отрезка не будет стремиться к нулю, хотя как видно из рисунка точка С к корню быстро приближается. Это приводит к 2 характерным особенностям конечного метода хорд:

На первой итерации необходимо выбрать неподвижный конец отрезка и соответствующую формулу. Далее вычисления ведутся только по этой формуле, а проверять условие F(a)*F(c)<0 нет необходимости.

Так как один конец отрезка не меняется, то точка С образует быстро сходящуюся последовательность значений С1, С2, С3, С4,…. Для оценки погрешности здесь используют косвенную оценку (как правило используемую в итерационных методах) d |Сk+1 - Сk|.

Сравнительная характеристика конечных методов

Конечные методы можно сравнивать по нескольким важным характеристикам:

Количеству итераций.

Сложности алгоритма.

Удобства реализации.

С точки зрения 1-го критерия метод дихотомии уступает методу хорд, который сходится быстрее. По другим характеристикам метод дихотомии существенно лучше. Его алгоритм прост, надежен и легко реализуем. Первый критерий становится важен только в задачах критичных по времени вычисления корня. В некоторых задачах корни вычисляются многократно (тысячи или десятки тысяч раз), тогда метод хорд имеет некоторые конкурентные преимущества.

5. Итерационные методы уточнения корней

Итерационные вычисления производятся по итерационным формулам, которые бывают двух видов:

явная формула x=f(x)

неявная формула F(x)=0.

Неявные формулы могут быть преобразованы к явному виду: x=С*F(x)+x, где С- константа, которая выбирается из условия сходимости метода. Явная формула может быть представлена в виде рекуррентной формулы, когда элемент xk последовательности выражается в виде xk =F(xk-1 , xk-2 …). Результатом вычисления по такой формуле является итерационная последовательность xk. Пределом последовательности является решение нашего уравнения.

Алгоритм вычисления по итерационной формуле:

Определение начального приближения из условия сходимости.

Организация вычисления последовательности по правилу:

x1 =f(x0) => x2 =f(x1) => … xn =f(xn-1 )

Прерывание вычислений производится при достижении косвенной оценки заданной погрешности

|xk+1 -xk | <

Метод простой итерации

В данном методе формула выражается в явном виде х=(x). Условие сходимости для этого метода определяется с помощью теоремы о сжимающем отображении (если отображение (x) удовлетворяет условию сжимаемости, то итерационная последовательность будет сходящейся). В одномерном случае будет простая формула для начального приближения х0: |'(x0)| < 1. В простейшем случае (x)= F(x)/n+x или (x)=-F(x)/n+x, n - положительно число. Если |F'(x)|>1, то n>1, если |F'(x)|<1, то n 1. Выбирая n можно практически всегда удовлетворить условие сходимости.

Замечание: Следует учитывать, что итерационная последовательность может сходиться к искомому корню, другому корню или расходится (уход значений на бесконечность). Нам необходим только первый вариант. Для этого нужно, чтобы вокруг искомого корня была область, в которой все точки удовлетворяют условию сходимости. Это несколько более сложное условие, чем |'(x0)| < 1 , которое определяется для 1 точки x0.

Рассмотрим это замечание на примере использования метода простой итерации для вычисления корней:

Таким образом, производная первой итерационной формулы x=y/x в близи корня близка к единице и метод не сходится. Если формулу преобразовать к виду x=(x+y/x)/2, то производная будет уже близка к нулю и метод будет не только сходится, но и сходится максимально быстро. Чем ближе производная к нулю, тем быстрее сходимость. Это свидетельствует о необходимости правильного выбора итерационной формулы и некоторого начального исследования области вокруг предполагаемого корня нелинейного уравнения. Теперь можно сформулировать итоговый порядок метода простой итерации:

Задается отрезок отделения корня и нелинейное уравнение.

Строится итерационная формула.

Исследуется сходимость построенной итерационной формулы на заданном отрезке. При необходимости формула корректируется. Для упрощения часто проверяется условие сходимости на концах отрезка, если там все в порядке, то считается, что на всем отрезке условие сходимости тоже выполняется.

Для выбранной формулы выбирается подходящее начальное приближение x0 . Для упрощения часто выбирается середина отрезка.

Производится вычисление итерационной последовательности до тех пор пока не будет выполнено условие выхода, которое определяется как d<, где d = |xk+1 -xk |.Тогда xk+1 - искомый корень нелинейного уравнения.

Данный алгоритм применим к любому итерационному методу, отличаются только итерационные формулы и условие сходимости. Более того, можно доказать что рассматриваемые далее итерационные методы - частные случаи метода простой итерации со специально выбранными итерационными формулами.

Итерационный метод хорд

Из формулы метода хорд можно построить итерационную формулу

Это частный случай метода простой итерации, поэтому условие сходимости можно определить как в этом методе, но лучше использовать условие сходимости метода Ньютона, поскольку метод хорд (в пределе) сходится к методу Ньютона. Главная особенность метода хорд - необходимость 2-х начальных условий для расчета по итерационной формуле, что явно не удобно для расчета на ЭВМ.

Метод Ньютона - Чебышева

Русский математик Чебышев предложил обобщить итерационные методы решения нелинейного уравнения путем вывода наилучших последовательных приближений.

Пусть задано нелинейное уравнение: и существует корень этого уравнения, который обозначим как xk.. Разложение в ряд Тейлора в точке корня имеет вид:

В первом приближении разложения в ряд получается метод Ньютона. Для более точных оценок Чебышев предложил раскладывать в ряд не функцию f, а обратную к ней функцию. Тогда такое разложение имеет вид:

Использование данной формулы, дает принципиальную возможность вычислить любое, сколь угодно точное приближение к корню.

Рассмотрим пример вычисления первого приближения:

=>

В терминах рекурсивных формул имеем:

Таким образом, в первом приближении метод Чебышева так же дает формулу метода Ньютона.

Рассмотрим пример вычисления второго приближения:

=>

=>

Второе же приближение можно уже назвать формулой Чебышева.

Рассмотрим теперь условия сходимости для этих приближений. Условия сходимости для метода Ньютона можно получить, если считать его частным случаем метода простой итерации. Получаем формулу:

При (x)=f/f' =>

Так как метод Ньютона - это 1-е приближение формулы Чебышева, то формула сходимости останется справедливой и для последующих, более точных приближений (обратное неверно - если метод Ньютона не сходится, то следующее приближение может в этой точке сходиться). Таким образом, на практике можно сходимость метода Чебышева оценивать по формуле для метода Ньютона.

Замечание: Можно считать метод Чебышева частным случаем метода простой итерации и вывести формулу точного условия сходимости, но эта формула сложна и для практических целей не удобна.

Комбинированный метод

Для реализации итерационных методов в ЭВМ некоторые из представленных итерационных методов модернизировали. Так, например, существует метод Ньютона с постоянной производной. В формуле Ньютона самое сложное для реализации на ЭВМ - вычислить производную. Ее приходится считать на каждой итерации. С другой стороны в близи корня (при малых изменениях x) производная меняется слабо. Это дало основание упростить алгоритм - производная вычисляется в начальной точке, а дальше считается неизменной. Алгоритм сходится медленнее, но вычисления на ЭВМ в результате часто даже ускоряются. Формула для этого метода

.

Другая модификация метода Ньютона заключается в установленном математиками факте отделения корня результатами вычисления по формулам Ньютона и хорд. Это значит, что если начальное приближение в обеих формулах одинаковое, то результат вычисления дает отрезок (между хк для Ньютона и хорд) на котором точно есть корень. Середина этого отрезка уточняет корень лучше чем оба используемых методов, кроме того метод получает дополнительную сходимость. Описанная процедура уточнения корня с помощью двух методов сразу получила название комбинированного метода. Он отличается исключительной скоростью уточнения.

Сравнительная характеристика итерационных методов

Конечные методы можно сравнивать по нескольким важным характеристикам:

Количеству итераций.

Сложности алгоритма.

Удобства реализации.

С точки зрения 1-го критерия можно построить некий рейтинг методов в порядке убывания их скорости вычисления - метод Чебышева, комбинированный метод, метод Ньютона, метод хорд, метод простой итерации. Конечно это некая усредненная характеристика, так как большинство из этих методов можно считать частным случаем одного метода - метода простой итерации. Можно например построить формулу в методе простой итерации, которая для частного случая конкретного уравнения будет сходиться быстрее формулы Чебышева. Однако практически это не выгодно, лучше иметь одну программу для разных уравнений. Таким образом, 2 и 3 критерий при реализации в ЭВМ часто более важны.

На практике компромисс между критериями чаще выигрывает метод Ньютона и его производный комбинированный метод. Метод Чебышева остается лучшим вариантом для ручных вычислений, когда не желательно иметь более 2 итераций. В простейших задачах используется и метод простой итерации.

6. Методы решения систем нелинейных уравнений

Задача решения Систем Нелинейных Уравнений (СНУ) не имеет конечных методов решения. Так или иначе, здесь используются итерационные методы. При этом решение СНУ - вектор в некотором многомерном пространстве. В этом случае процедура отделения корней значительно усложняется и как правило требует отдельного математического анализа для каждой конкретной задачи. Будем считать, что эта задача уже решена и выделена некая многомерная область, в которой есть только один вектор решения СНУ. Тогда существует 2 альтернативных подхода к решению СНУ:

Сведение к задаче нелинейной оптимизации.

Использование итерационных методов.

Метод сведения к задаче нелинейной оптимизации заключается в следующем преобразовании задачи:

Пусть задана СНУ fi (x1, x2, …, xn) = 0, где i = 1,2,3,…- номер нелинейного уравнения. В векторном виде эта задача запишется как F(X) =0. Составим сумму квадратов наших уравнений и назовем ее величиной М = ? fi2. Очевидно, что при равенстве нулю всех fi величина М тоже будет равна нулю. При этом М всегда больше или равна нулю (так как это сумма квадратов). Это означает, что минимум М тоже равен нулю. Таким образом, если существует решение СНУ, то оно совпадает с минимумом М. Мы свели решение СНУ к решению задачи поиска минимума - задачи оптимизации.

Нелинейные задачи оптимизации имеют свои собственные методы решения. В данном случае это многомерная задача безусловной оптимизации. Наиболее известные методы ее численного решения - метод координатного поиска, метод градиентного поиска, метод случайного поиска.

Метод случайного поиска наиболее прост - генерируются множество случайных точек в области поиска, в каждой точке вычисляется значение функции. Сравнивая эти значения можно найти минимальное значение. Чем больше точек, тем точнее этот метод. Существуют и модификации этого метода. В основном они заключаются в использовании «окна» - части области поиска. Если точки выбирать внутри окна, то плотность точек и точность метода увеличиваются. Затем это окно можно перемещать так, чтобы найденное лучшее значение всегда было в центре окна. В других вариантах окно постепенно уменьшается.

Другие методы многомерного нелинейного поиска - градиентный поиск (метод наискорейшего спуска), координатный поиск используют методы одномерного поиска. Суть их в том, чтобы выбрать некую прямую и искать максимум на этой прямой одномерным методом. В методе координатной релаксации эти прямые берутся вдоль координатных осей. Фиксируются все переменные, кроме одной и ищется максимум. Затем найденные значения фиксируются, освобождается другая переменная и так до тех пор, пока расстояние между найденными точками не будет меньше погрешности.

Градиентный поиск подобен предыдущему. Отличие только в том, что прямая выбирается вдоль направления градиента. Главное свойство вектора градиента функции ы том, что он всегда направлен в сторону возрастания функции.

Среди одномерных методов можно назвать метод половинного деления, чисел Фибоначчи и золотого сечения. Суть методов - внутри отрезка оставляем только один максимум или один минимум. Этот отрезок называют унимодальным. Выбираются две точки внутри. Находят в них значение функции, а дальше одну из частей отбрасывают. Этим данные методы очень похожи на метод дихотомии. В них реализуется общая идея уменьшения отрезка неопределенности.

В методе половинного деления точки берутся симметрично относительно середины отрезка на небольшом расстоянии. В методе золотого сечения точки берутся в соответствии с правилом золотого сечения - отношение большей части b отрезка к меньшей части a равно отношению всего отрезка (b+a) к большей части (b/a = (b+a)/b). В методе чисел Фибоначчи точки берутся в отношении чисел Фибоначчи

ci+1 = ci + ci-1 => ci / ci+1 + ci-1 / ci+1 =1 => умножим на длину отрезка р => сечение р*ci/ci+1 + р*ci-1/ci+1 =р.

Отношение чисел Фибоначчи в пределе стремится к золотому сечению, поэтому эти методы взаимосвязаны.

Итерационные методы решения СНУ

К итерационным методам решения СНУ относят прежде всего метод простой итерации и метод Ньютона.

Метод простой итерации

В методе простой итерации система уравнений fi (x1, x2, …, xn) = 0 выражается в виде: xt (k+1) = цi(xt (k)) или в векторном виде X (k+1) = цi(X (k))

Возможности такого представления обсуждались ранее при изучении метода простой итерации решения одного уравнения. Выбрав начальный вектор X (0), можно по итерационным формулам построить последовательность X (k) . Теперь нужно определить условие выхода из итерационного процесса (аналогично варианту одного уравнения). Таким условием будет служить косвенная оценка погрешности с использованием нормы векторов: || X (k+1) - X (k)|| < е (заданная абсолютная погрешность)

Условие сходимости для метода простой итерации является условием существования сжимающего отображения: || ц(А) - ц(В)|| < k*|| А - В)|| ,для любых векторов A, B, и коэффициентов 0<k<1.

Метод Ньютона

Система уравнений fi (x1, x2, …, xn) = 0 можно в векторной форме представить как F(X)=0, где F(X)- векторная функция, X - произвольный вектор.

Разложим в ряд Тейлора эту векторную функцию и в первом приближении получим:

-

первое приближение. Введем понятие матрицы Якоби J:

- матрица Якоби (содержит частные производные функций fi , причем строке матрицы соответствует одна функция, а столбцу производная по одной из переменных).

Теперь матричное представление первого приближения будет следующим:

F(X) = F(X0) + J(X0)* (X - X0)

Пусть вектор X соответствует решению СНУ (корень), тогда F(x)=0, тогда получим:

F(X0) = J(X0)* (X0 - X)

С помощью этого выражения строим итерационную формулу метода Ньютона:

X = X0 - J-1(X0)* F(X0) => X(k+1) = X(k) - J-1(X(k))* F(X(k))

Здесь J-1 - обратная матрица для матрицы Якоби.

Для того, чтобы пользоваться методом Ньютона необходимо определить условие сходимости для выбора начального приближения. Существует доказательство метода сходимости при наличии трех условий:

1. ||F(A)-F(C) - J(C)*(A-C)|| / || C-A ||2 - конечно для любых A и C.

Данное условие в принципе выполняется, если все функции конечны на заданном отрезке, непрерывны и бесконечное число раз дифференцируемы.

2. ||J(C)|| - норма матрицы Якоби конечна.

3. det(J) ? 0 - определитель матрицы Якоби не равен нулю.

Замечание: первое и второе условие практически всегда выполняются для стандартных функций, а третье условие выполняется далеко не всегда. Для того, чтобы оно выполнялось, мы должны выбрать начального приближение так, чтобы det(J(X(0))) ? 0

Литература

1. Бахвалов Н. и др. Численные методы. - М.: Лаборатория базовых знаний. 2000.-624с.

2. Бахвалов Н.С. и др. Численные методы в задачах и упражнениях. -М.:Высшая школа.2000. -190с.

3. Вержбицкий В.М. Численные методы. Математический анализ и ОДУ.-М.: Высшая школа. 2001. -382 с.

4. Вержбицкий В.М. Численные методы. Линейная алгебра и нелинейные уравнения.-М.: Высшая школа. 2000. -266 с.

5. Гриненко Е.В., Емельянова М.В., Пушечкин Н.П. Численные методы (учебно-методическое пособие).- Славянск-на-Кубани. ч.1 ООО «Берегиня». 2003. -64 с. ч.2 Изд. СГПИ. 2005. -56 с.

Размещено на Allbest.ru

...