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

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

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

1. Основные сведения о системах нелинейных уравнений в

Общая форма систем нелинейных уравнений в имеет вид:

(5.1)

где

заданные функции n переменных, - неизвестные.

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

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

Частным случаем системы (5.1) является система линейных уравнений:

,

Где, А - матрица, порождающая линейный оператор, отображающий

в .

Системе линейных уравнений (5.1) поставим в соответствие линеаризованное уравнение (первые два члена из разложения в ряд Тейлора (5.1)) в точке вида

(5.2)

,

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

Для дальнейшего нам потребуется еще одна форма записи системы нелинейных уравнений в , а именно:

(5.3)

где .

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

Функции удовлетворяют тем же условиям, что и функции .

2. Отделение решений

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

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

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

Безусловно, графические построения имеют большие погрешности, и выбранные начальные приближения могут не попасть в область сходимости применяемого метода. В таких случаях нужно провести пробные решения на ЭВМ выбранным методом с исследованием сходимости.

Если приближения сходятся, то начальные приближения выбраны в области сходимости метода и можно получить приближенное решение с заданной точностью.

Если приближения расходятся, следует провести более точные графические построения и выбрать начальное приближение в области сходимости.

Аналогично отделяются решения для системы двух нелинейных уравнений

,

.

В этом случае на плоскости x,y строятся линии уровня функции двух переменных и . Координаты точек пересечения графиков этих функций дают начальные приближения изолированных решений. 5.3. Методы решения нелинейных уравнений Метод простой итерации

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

Для применения метода простой итерации система уравнений (5.1) приводится к виду (5.3).

Затем, взяв начальное приближение , которое предполагается либо известным, либо произвольным, строим последовательность по следующим формулам

(5.4)

(5.5)

Замечание. Для приведения системы уравнений (5.1) к виду (5.3) можно использовать прием:

где - релаксационный параметр. Метод Зейделя

Метод Зейделя отличается от метода простой итерации тем, что вычисления ведутся по формулам:

(5.6)

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

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

Этот метод предложен И.Ньютоном в 1669 году, однако наиболее полное обоснование было сделано советским математиком Л.В.Канторовичем в 1949 году, поэтому в литературе этот метод часто называют методом Ньютона-Канторовича.

Метод Ньютона является одним из итерационных методов, получаемых линеаризацией линейного оператора ,

где из уравнения (5.1).

Так, для к-го приближения точному решению уравнения (5.1) ставится в соответствие линеаризованное уравнение вида (5.2), а именно:

,

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

,

.

метод решение нелинейный уравнение

Таким образом, последовательность (5.4) строится по следующим правилам: , (5.7)

.

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

Итерационная формула метода Ньютона при таком подходе будет иметь вид:

(5.8)

Модифицированный метод Ньютона

Эта разновидность метода Ньютона строится путем определения производной только в одной точке приближенного решения, т. е. последовательные приближения (5.4) строятся по формулам:

, (5.9)

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

Итерационная формула для построения приближенного решения нелинейного уравнения (5.1) на основе линеаризованного уравнения (5.7)

имеет вид:

Метод наискорейшего спуска

Методы спуска сводят решение системы (5.1) к задаче нахождения минимума специально построенного функционала (функционал - отображение в R), а именно:

,

где .

Функционал в конечном пространстве Rn можно рассматривать как функцию многих переменных .

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

В итерационной формуле параметр hk пока не определен, выберем его таким образом, чтобы выполнилось условие: , начиная с x0, в предположении, что - монотонный функционал.

Для выбора hk построим функционал, зависящий от параметра, который изменяется непрерывно:

.

При h=0 имеем, что (0) - линия уровня функционала, проходящая через точку xk . Для нахождения следующей линии уровня, более близкой к минимуму, будем выбирать h таким образом, чтобы для данного xk

.

Это условие минимума по h будем рассматривать как уравнение для получения hk.

Решим его приближенно, т.к. ошибка в несколько процентов обычно не влияет на скорость сходимости. Отметим кстати, что число hk всегда должно быть положительным. Для этого разложим функцию в ряд Тейлора по h в точке h=0 и возьмем только линейную часть этого разложения

.

Подстановка линейной части в условие дает уравнение для приближенного определения

.

Решая построенное уравнение относительно h, получим:

.

Таким образом, итерационная формула метода наискорейшего спуска имеет вид:

,

где производные вычислены в точке .

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

,

.

4. Сходимость методов решения нелинейных уравнений

Если метод сходится, то есть

,

где - точное решение,

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

,

где - заданная точность (погрешность).

Однако практически это условие выполнить нельзя, так как неизвестно, тогда для окончания итерационного процесса можно воспользоваться неравенствами

,

,

где и - заданные величины.

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

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

,

где - константа, своя у каждого метода, зависящая от выбора начального приближения , функции fi , i = 1, 2, . . . , n, и их частных производных первого и второго порядков - точнее, их оценок в некоторой окрестности искомого решения, которой принадлежит начальное приближение.

Метод Ньютона является методом второго порядка, то есть для него имеет место неравенство

,

где - константа, зависящая от тех же величин, что и константа .

А теперь рассмотрим достаточные условия сходимости метода простой итерации и метода Ньютона.

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

Второе условие связано с матрицей, составленной из частных производных первого порядка функций 1, 2, . . . , n - матрицей Якоби

,

вычисленной в точке .

В случае, когда рассматривается система линейных алгебраических уравнений, матрица M состоит из постоянных чисел - коэффициентов, стоящих при неизвестных в правой части уравнения (5.3). В случае нелинейных уравнений элементы матрицы M зависят, вообще говоря, от .

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

Приведем также достаточные условия сходимости метода Ньютона для системы уравнений вида (5.1) по норме .

Понятие о нелинейных системах уравнений в Rn.

1. Понятие приближенного и точного решений нелинейной системы уравнений.

2. Сущность графического метода отделения решения для системы двух нелинейных уравнений. Каковы его преимущества и недостатки?

3. Сущность метода простой итерации и метода Зейделя. Каковы условия применимости метода простой итерации?

4. Сущность метода Ньютона и его модификации. Какова скорость сходимости метода Ньютона?

5. Сущность метода наискорейшего спуска. Как выбирается параметр спуска?

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