86108 (597869), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

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

(4)

по следующим формулам

(5)

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

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

4.2 Метод Зейделя

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

(6)

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

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

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

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

,

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

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

или ,

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

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

(),

где – обратный оператор к линейному оператору , определяемому квадратной матрицей

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

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

(7)

. (8)

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

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

, (9)

где – начальное приближение к точному решению .

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

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

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

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

,

где .

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

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

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

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

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

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

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

.

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

.

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

или .

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

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

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

, т.е. .

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

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

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

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

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

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

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

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

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

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

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

,

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

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

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

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

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

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

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

1. Выполнено неравенство

,

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

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

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

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

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

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

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

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

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

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

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

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

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, начальное приближение выбрать произвольно или графически, (0,1).

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

Характеристики

Список файлов книги