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

Итерационные методы решения СЛУ сводятся к поиску вектора , минимизирующего функцию.

Воспользуемся теорией ФНП из мат.анализа:

–вектор, в направлении которого скорость возрастания наибольшая.

, где – частная производная по переменнойl.

Получаем рекуррентную формулу:

(6),

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

.

Особый случай.

Пусть A – симметричная и положительно определенная матрица.

Пусть .

Точка минимума такой функции является решением уравнения .

Доказывается подстановкой и по определению – пропускаем.

Тогда .

.

Пусть .

, где – параметр, определяемый из условия:

.

Выведем формулу для нахождения .

Рассмотрим

(т.к. A – симметричная, то

Т.о. – квадратная функция с положительным коэффициентом при.

(т.к. A – положительно определенная, то для любого)

в точке минимума.

–значение, при котором .

§ 3. Обратная интерполяция для решения нелинейных уравнений

Задача: Дано: f(x) = 0

Найти: x₀, такой, что f(x₀)=0.

Пусть точное решение x_T  [a,b] и f(x) обратима на [a,b], т.е. существует обратная функция g(x) = f^–1(x): g(f(x))=x.

Тогда g(0)=g(f(x_T))=x_T.

Алгоритм:

1) Выбрать [a,b]: f(x) обратима (монотонна).

2) Выбрать узлы x₀, ..., x_n  [a,b].

Вычислить значения f(x) в узлах: f(x₀), ..., f(x_n).

3) Для g(x): f(x₀), ..., f(x_n) — узлы

x₀, ..., x_n — значения в узлах.

Найти интерполяционный многочлен L_n(x)  g(x).

4) L_n(0)  g(0) = x_T — приближенное значение корня уравнения.

§ 4. Системы нелинейных уравнений: метод простых итераций

Задача: Дано: (7),

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

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

1) Преобразовать уравнение (7) в уравнение вида (8) ;

2) Составить рекуррентную формулу: (9);

3) Выбрать любое начальное приближение . По формуле (9) найти,, …,;

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

Опр. Метрическое пространство H — множество, на котором задана функция метрики (расстояния) (a,b), удовлетворяющая условиям:

1) (a,b)  0, и (a,b) = 0  a = b;

2) (a,b) = (b,a);

3) (a,b) + (b,c)  (a,c).

В нашем случае H = ⁿ, .

Опр. Отображением в метрическом пространстве называется функция

g : H  H.

Опр. Отображение называется сжимающим, если существует число q:

0 ≤ q < 1, такое, что для любых x₁, x₂  H выполняется

(g(x₁),g(x₂)) ≤ q(x₁, x₂).

Теорема.

Если отображение является сжимающим, то уравнениеимеет единственное решениеи.

Док-во:

1. Поскольку является сжимающим, то

(обозначили ).

Тогда для l > k выполняется

Т.о. при l  , k   выполняется , следовательно последовательность ,, …,,… сходится к предельному значению.

2.

.

Это неравенство верно для любого k, т.е. меньше сколь угодно маленького положительного числа, т.е..

Следовательно, — точное решение уравнения (8).

3. Предположим, что уравнение (8) имеет два точных решения и.

.

.

Теорема доказана.

Частный случай. Пусть n = 1, т.е. система состоит из одного уравнения

f(x) = 0 с одной неизвестной x.

Уравнению равносильно x = g(x). Решение x_T — точка пересечения графиков функций y = x и y = g(x).

x₁ = g(x₀), x₂ = g(x₁), …

На этом рисунке метод простых итераций сходится.

На следующем — нет.

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

.