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

4.5 Метод Зейделя на основе линеаризованного уравнения

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

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

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

,

где .

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

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

В итерационной формуле параметр h_k пока не определен, выберем его таким образом, чтобы выполнилось условие: , начиная с x⁰, в предположении, что f – монотонный функционал.

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

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

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

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

.

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

.

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

 или .

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

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

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

, т.е. .

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

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

 – точное решение

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

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

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

Методы простой итерации, Зейделя, модифицированный метод Ньютона, метод наискорейшего спуска (см. [1], [2], [3], [4]) являются методами первого порядка – это значит, что имеет место неравенство , k=1, 2, . . . , где  – константа, своя у каждого метода, зависящая от выбора начального приближения , функции f_i, i = 1, 2, . . . , n, и их частных производных первого и второго порядков – точнее их оценок в некоторой окрестности искомого решения, которой принадлежит начальное приближение.

Метод Ньютона является методом второго порядка, то есть для него имеет место неравенство , k=1, 2, . . . , где  – константа, зависящая от тех же величин, что и константа .

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

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

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

 ,

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

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

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

Предположим, что имеется начальное приближение к искомому решению системы (2) , функции  непрерывны и имеют непрерывные частные производные до второго порядка в шаре , тогда, если выполнены условия:

1)  Матрица Якоби  системы (2) на начальном приближении имеет обратную  и известна оценка нормы обратной матрицы ,

2)  Для всех точек шара  выполнено неравенство

 при i, j = 1, 2, . . . , n ,

3)  Выполнено неравенство

,

где L – постоянная 0 £ L £ 1,

4)  Числа b, N, r подчинены условию a = nbNr < 0,4, тогда система уравнений (2) в шаре  имеет единственное решение, к которому сходятся последовательные приближения (8) или (7’), (9’).

Для других методов условия сходимости имеют сложный вид, и мы отсылаем читателя к специальной литературе [1], [2], [3], [4].

6. Примерный перечень возможных исследований

1)  Сравнение различных методов на экономичность при решении конкретной задачи:

·  по числу операций на одной итерации;

·  по числу итераций, необходимых для достижения заданной точности;

2)  Зависимость числа итераций для достижения заданной точности:

·  от выбора вида нормы;

·  от выбора критерия окончания итерационного процесса по  или по невязке  ;

·  от выбора начального приближения;

·  от погрешности задания коэффициентов в уравнении.

7. Контрольные вопросы

1)  Понятие о нелинейных системах уравнений в Rⁿ.

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

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

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

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

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

8. Порядок выполнения курсовой работы

1)  Получить вариант задания, индивидуальный для каждого студента, у преподавателя, а именно:

Найти решение системы нелинейных уравнений в первой координатной четверти с номером – N₁ (см. варианты заданий п.10), применив для первого этапа уточнения метод с номером – N₂, а для второго этапа уточнения метод с номером – N₃ , точность вычислений на первом этапе – EPS1Î[0.1 – 0.01], на втором этапе – EPS2 Î [0.1 - 0.0001], N₄ – номер нормы, I – номер параметра a, J – номер параметра b, начальное приближение выбрать произвольно или графически, aÎ(0,1).

2)  Разработать обязательные для выполнения задания разделы данных методических указаний.