Численные Методы, 12 лекция (от 26 марта)

Материал из eSyr's wiki.

Версия от 14:27, 22 июня 2007; Esyr01 (Обсуждение)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Предыдущая лекция | Следующая лекция

Содержание

Глава 3. Численное решение нелинейных уравнений и систем нелинейных уравнений

Параграф 1. Введение

f(x) = 0, x — вещественное (1)

Если f(x) нелинейна, то решить аналитически такую задачу удаётся в крайне редких случаях.

Будет рассмотрен ряд методов, они будут обоснованы, будут указаны основные их характеристики.

На f будем требовать только гладкость.

Если берём x вещественное, то не освобождаемся от комплексных корней, поэтому предполагаются комплексные корни.

  1. Локализация корня x*, f(x*) = 0, указать область, где он находится. Этим мы заниматься не будем.
  2. Строится итерационный процесс, и аккуратно выбирая начальное приближение 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


Календарь

Февраль
пн
12 19
вт
13 20 27
Март
пн
05 12 19 26
вт
06 13 20 27
Апрель
пн
02 09 16 23 29
вт
03 10 17 24

Дополнительная информация

Содержание курса | Задачи на лекциях

Материалы к экзамену

Вопросы по курсу | Определения


Эта статья является конспектом лекции.

Эта статья ещё не вычитана. Пожалуйста, вычитайте её и исправьте ошибки, если они есть.
Личные инструменты
Разделы