Численные Методы, 12 лекция (от 26 марта)
Материал из eSyr's wiki.
Предыдущая лекция | Следующая лекция
Содержание |
[править] Глава 3. Численное решение нелинейных уравнений и систем нелинейных уравнений
[править] Параграф 1. Введение
f(x) = 0, x — вещественное (1)
Если f(x) нелинейна, то решить аналитически такую задачу удаётся в крайне редких случаях.
Будет рассмотрен ряд методов, они будут обоснованы, будут указаны основные их характеристики.
На f будем требовать только гладкость.
Если берём x вещественное, то не освобождаемся от комплексных корней, поэтому предполагаются комплексные корни.
- Локализация корня x*, f(x*) = 0, указать область, где он находится. Этим мы заниматься не будем.
- Строится итерационный процесс, и аккуратно выбирая начальное приближение x0 из локализованной области, xn → x*, n → ∞.
[править] Нелинейная система
| { | f1(x1, x2, …, xm) = 0 |
| f2(x1, x2, …, xm) = 0 | |
| … | |
| fm(x1, x2, …, xm) = 0 |
- f: Rm → Rm
- f_ = (f1, …, fm)T
- x_ = (x1, …, xm)T
- f_ (x_) = 0
[править] Методы
[править] Самый простой метод
Пусть корень вещественный. Тогда самый простой метод — разбить отрезок на несколько. Тогда если знак на каком-то из отрезков меняется, то на нём есть нечётное число корней, и его можно разбить ещё. Если же знак не меняется, то там либо нет корней, либо чётное их количество.
[править] Метод бисекции
Второй метод более регулярный и он называется метод бисекции.
- f(a) < 0
- f(b) > 0
- Берётся x0 = (a + b)/2
- Если f(x0) > 0, то x* ∈ (a, x0)
Каждый раз мы сужаем в два раза промежуток, где находится корень
[править] Начальное приближение
Ведём понятие окрестности корня:
- Ua(x*) = {x: |x − x*| < a}
Начальное приближение будем брать в окрестности корня
[править] Параграф 2. Метод простой итерации (МПИ)
- f(x) = 0 (1)
- x* ∈ Ua(x*) (по определению)
- x = S(x) (2)
- xn + 1 = S(xn) (3)
- x0 ∈(x*)
S(x) выбирается следующим образом: S(x) = x + r(x)f(x) (4). Единственное требование на r(x): sign(r(x)) ≠ 0 при x ∈ Ua(x*).
Говорят, что S(x)Липшиц-непрерывна (удовлетворпяет условию Лиешица с константой q), x ∈ Ua(x*), ∀ x1, x2 ∈ Ua(x*): |S(x1) − S(x2)| ≤ q|x1 − x2|
Это условие сильнее непрерывности и слабее дифференцируемости.
Утверждение. Пусть S(x) — Липшиц-непрерывна с 0 < q < 1. Тогда МПИ сходится для ∀ x0 ∈ Ua(x*) со скоростью геометрической функции.
Доказательство. Методом матиндукции
- |x0 − x*| < a
- |xn − x*| < a
- |xn + 1 − x*| < q|xn − x*|
- |xn + 1 − x*| = |S(xn) − S(x*)| < q|xn − x*|
Понятно, что эту формулу можно трактовать как рекуррентную, и тогда
- |xn − x*| < qn|x0 − x*|
- limn → ∞qn = 0 ⇒ xn → x*
Замечание 1. Если известно, что ∃ S'(x), и supx ∈ Ua(x*) |S'(x)| = q < 1, то МПИ сходится, x0 ∈ Ua(x*)
Замечание 2. Расмотрим МПИ, записанный следующим образом:
- (xn + 1 − xn)/τ + f(xn) = 0, τ > 0, x0 ∈ Ua(x*), n = 0, 1, 2, … (5)
- ∃ f'(x), M1 = supx ∈ Ua(x*) |f'(x)|
- S(x) = x − τf(x)
- Продифференцируем: S'(x) = 1 − τf'(x). Если модуль |S'(x)| < 1, то МПИ сходится. Найдём условия на τ:
- −1 < 1 − τf'(x) < 1 ⇒ 0 < τ < 2/M1
Так что если в итерационном методе (5) будем выбирать τ в границах, указанных выше, то получим сходимость со скоростью геометрической прогрессии.
[править] Метод Эйткена ускоренной сходимости
Предположим, что xn − x* = Aqn (6). Запишем три итерации:
- xn − 1 − x* = Aqn − 1 (7)
- xn − x* = Aqn (8)
- xn + 1 − x* = Aqn +1 (9)
Тогда:
- xn + 1 = x* + Aqn + 1
- x* = xn + 1 − Aqn + 1
- (xn + 1 − xn)2 = A2q2n(q − 1)2
- xn + 1 − 2xn + xn − 1 = Aqn − 1(q − 1)2
- ((xn + 1 − xn)2)/(xn + 1 − 2xn + xn − 1) = Aqn − 1
- x* = xn − ((xn + 1 − xn)2)/(xn + 1 − 2xn + xn − 1)
Но так как (6) неточно, то это оказывается хоть и достаточно точным, но приближением.
Замечание. Неважно, какой метод мы ускоряем, главное, чтобы он был записан в виде (6).
[править] Параграф 3. Метод Ньютона (касательных) и метод секущих
Нас неудовлетворяет метод простой итерации, медленная сходимость.
- f(x) = 0 (1)
- x* ∈ Ua(x*) (по определению)
- xn — n-я итерация
- xn + 1 = xn − f(xn)/f'(xn), n = 0, 1, …, x0 — начальное приближение (2)
- От функции требуется гладкость до третьей производной
Метод Ньютона очень быстро сходится, но он может зацикливаться.
Модифицированный метод Ньютона:
- xn + 1 = xn − f(xn)/f'(x0), n = 0, 1, …, x0 — начальная итерация
- Скорость сходимости колеблется, но производительность повышается (особенно в системах) и позволяет избежать зацикливания
[править] Вывод метода Ньютона
- 0 = f(*) = f(x) + (x* − x)f'(x)
- x→ xn
- x* → xn + 1
- f(xn) + (xn + 1 − xn)f'(xn) = 0
- xn + 1 = xn − f(xn)/f'(xn)
Начальное приближение выбираем очень и очень жёстко.
[править] Вывод метода Ньютона для системы уравнений
[править] Частный случай для двух уравнений
| { | f1(x1, x2) = 0 | (3) |
| f2(x1, x2) = 0 |
(x1*, x2*) — решение
- 0 = f1(x1*, x2*) = f(x1, x2) + (x1* − x1) (δf1/δx1)(x1, x2) + (x2* − x2) (δf2/δx2)(x1, x2)
- xi → xin
- xi* → xin + 1
| { | f1(x1n, x2n) + (x1n + 1 − x1n) (δf1/δx1)(x1n, x2n) + (x2n + 1 − x2n) (δf1/δx2)(x1n, x2n) = 0 | (4) |
| f2(x1n, x2n) + (x1n + 1 − x1n) (δf2/δx1)(x1n, x2n) + (x2n + 1 − x2n) (δf2/δx2)(x1n, x2n) = 0 |
| J(x) = ( | (δf1/δx1)(x1n, x2n) | (δf1/δx2)(x1n, x2n) | ) |
| (δf2/δx1)(x1n, x2n) | (δf2/δx2)(x1n, x2n) |
- f = (f1, f2)T
- xn = (x1n, x2n)
- f(xn) + J(xn)(xn + 1 − xn) = 0
- ∃ J−1(xn)
- xn + 1 = xn − J−1(xn)f(xn), n = 0, 1, …, x0 ∈ Ua(x*) (5)
[править] Общий случай для m уравнений
| { | f1(x1, x2, …, xm) = 0 | (6) |
| f2(x1, x2, …, xm) = 0 | ||
| … | ||
| fm(x1, x2, …, xm) = 0 |
- (J(x))ij = (δfi/δxj), i, j = 1…m
- xn + 1 = xn − J−1(xn)f(xn), n = 0, 1, …, x0 ∈ Ua(x*) (6)
- xn + 1 = xn − J(x0)f(xn)
[править] Метод секущей (хорд)
- xn + 1 = xn − f(xn)/f'(x0), n = 0, 1, …
- f'(xn) = (f(xn + 1) − f(xn))/(xn + 1 − xn)
Подставим в метод Ньютона приближение производной:
- xn + 1 = xn − (xn − xn − 1)f(xn)/(f(xn) − f(xn − 1))
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22
Календарь
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Дополнительная информация |
Материалы к экзамену |
