Научная литература
booksshare.net -> Добавить материал -> Физика -> Федоренко Р.П. -> "Введение в вычислительную физику" -> 4

Введение в вычислительную физику - Федоренко Р.П.

Федоренко Р.П. Введение в вычислительную физику — М.: Физ-тех, 1994. — 528 c.
ISBN 5-7417-0002-0
Скачать (прямая ссылка): vvedenievvichesleniyah1994.djvu
Предыдущая << 1 .. 2 3 < 4 > 5 6 7 8 9 10 .. 210 >> Следующая

10

ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ

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

В методе Ньютона, начиная с некоторого начального приближения х°, последовательно находятся точки х1, х2, ..., хк, ... таким образом, что Iim f(xk) = 0, a Iim хк = х*, где х* — решение систе-к.-*™

мы (1).

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

Рассмотрим стандартный шаг итерационного процесса метода Ньютона. Пусть имеется некоторое уже найденное приближение хк; следующее приближение хк+{ ищем в виде X* + 1 = Xk + Ьх, где 6х — малая поправка, уточняющая хк. Для ее определения выпишем уравнение f(xk + Ьх) = 0. Само по себе оно не проще исходного уравнения (1), но, используя предположение о малости Ьх, его можно линеаризовать, т.е. использовать разложение / по Ьх с точностью только до членов первого порядка:

f(xk + dx) = f(xk) + fx(xk) Ьх + 0(116х||2).

Пренебрегая членами 0(||6х||2), получаем линеаризованное уравнение для Ьх:

/(**) + /*(**) 6х = 0, (3)

которое уже решаемся, и можно выписать его явное решение:

Ьх = —f~l(xk) f(xk).

Итак, алгоритм метода Ньютона (MH) имеет следующую форму:

1) имеется некоторое уже найденное приближение х;

2) вычисляются вектор /(х) и матрица /Х(х);

3) решается система (линейных) уравнений (3);

4) пересчитывается приближенное решение х ¦= х + 6х.

Далее процесс повторяется циклически до получения достаточно малой величины ||/(дс) ||.

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

1. Что такое /х? Это есть производная вектЬр-функции по векторному аргументу. Точный смысл fх определяется первым членом
§ 1]

ряда Тейлора

РЕШЕНИЕ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ

f(x + дх) « f(x) + /Х(х) Ьх.

11

Это — векторная форма записи отрезков ряда Тейлора для всех п функций:

э/, а/. а/,

Z1O1, ..., х„) + — Sx1 + — Ьхг + ... + — Ьхп,

Эх,

Эх,

8/,

Sfn

^fn

fn(xt, Xn) +Trbxl+-f Ьх2 + ...+^f Ьхп.

Отсюда следует расшифровка:

9Jl

дх,

!L

дхы

Нл

дх,

9M

дх_

2. В теоретических оценках будем использовать явную форму

Ьх = —/,

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

При п = 1 метод Ньютона известен как «метод касательных». Этот термин поясняет рис. 1. Линеаризация состоит в том, что кривая у = f(x) заменяется касательной, проведенной в уже найденной точке хк, а « качестве следующего приближения хк+1 берется пересечение касательной с осью абсцисс. На рис. 1 показано несколько таких итераций и, естественно, возникает предположение о том, что процесс должен быть достаточно эффективным. Это и подтверждается более точным исследованием.

Рис. 1
12 ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ [Ч. I

Сходимость метода Ньютона. Докажем теорему о квадратичной сходимости метода.

Теорема 1. Пусть х* — решение системы (1). Предположим, что в некоторой окрестности х*:

а) /(х) является гладкой функцией в том смысле, что существуют ее производные до второго порядка и имеет место оценка И/„(*)Н«С2;

б) отображение х-*/(х) равномерно невырождено в том смысле, что f~l(x) существует и ограничена: ||/“'(х)|| < C1.

Тогда, если начальное приближение х° достаточно близко к х*, метод Ньютона сходится и имеет квадратичную скорость сходимости.

Точный аналитический смысл выражений «квадратичная скорость сходимости», «х° достаточно близко к х*», «Hf xxil =S С2» выяснится в процессе доказательства.

Доказательство. Будем следить за эволюцией в процессе итераций величины ||/(х*)|| (нормы невязки). Установим связь менаду Н/(**+1)И и ||/(**)||:

f(xk+l) = /(xk) + /,(**) Sx + OdISxII2).

Используя выражение Sx = —f~l(xk) f(xk) и оценку ||0(||Sx||2) || < *? C2 И Sx К 2 (именно в этом смысле понимается предположение а) теоремы), получаем

f(xk+l) = O(I)SxII2) = O(I)/;1 /И2),

откуда

ll/(x*+1)Il =S C2II/;1 /II2 =S C2Cf ||/(х‘)Il2

Обозначая rk = ||/(х*)||, имеем основное соотношение:

rk+i<Crl> 1^e C=C2C2 Эта оценка порождает следующую цепочку:

T1 =S Cr2, Г2 sS Crf =S Сгг*, к2 ^ Cr\ ^ C7г*.

Без труда угадываем общую форму:

rk ^ C-HCr0)2*.

Именно эту формулу (с показателем 2к) имеют в виду, когда говорят о квадратичной скорости сходимости.
Предыдущая << 1 .. 2 3 < 4 > 5 6 7 8 9 10 .. 210 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed