Численные Методы, 12 лекция (от 26 марта)
Материал из eSyr's wiki.
(Содержимое страницы заменено на «== From Ebaums Inc to MurkLoar. == We at EbaumsWorld consider you as disgrace of human race. Your faggotry level exceeded any imaginab...») |
(→Метод Эйткена ускоренной сходимости) |
||
(1 промежуточная версия не показана) | |||
Строка 1: | Строка 1: | ||
- | == | + | [[Численные Методы, 11 лекция (от 20 марта)|Предыдущая лекция]] | [[Численные Методы, 13 лекция (от 27 марта)|Следующая лекция]] |
- | + | ||
- | + | = Глава 3. Численное решение нелинейных уравнений и систем нелинейных уравнений = | |
- | + | == Параграф 1. Введение == | |
+ | f(x) = 0, x — вещественное (1) | ||
+ | |||
+ | Если f(x) нелинейна, то решить аналитически такую задачу удаётся в крайне редких случаях. | ||
+ | |||
+ | Будет рассмотрен ряд методов, они будут обоснованы, будут указаны основные их характеристики. | ||
+ | |||
+ | На f будем требовать только гладкость. | ||
+ | |||
+ | Если берём x вещественное, то не освобождаемся от комплексных корней, поэтому предполагаются комплексные корни. | ||
+ | |||
+ | # Локализация корня x<sub>*</sub>, f(x<sub>*</sub>) = 0, указать область, где он находится. Этим мы заниматься не будем. | ||
+ | # Строится итерационный процесс, и аккуратно выбирая начальное приближение x<sub>0</sub> из локализованной области, x<sub>n</sub> → x<sub>*</sub>, n → ∞. | ||
+ | |||
+ | === Нелинейная система === | ||
+ | {| | ||
+ | |rowspan = "4"|{ | ||
+ | |f<sub>1</sub>(x<sub>1</sub>, x<sub>2</sub>, …, x<sub>m</sub>) = 0 | ||
+ | |- | ||
+ | |f<sub>2</sub>(x<sub>1</sub>, x<sub>2</sub>, …, x<sub>m</sub>) = 0 | ||
+ | |- | ||
+ | |… | ||
+ | |- | ||
+ | |f<sub>m</sub>(x<sub>1</sub>, x<sub>2</sub>, …, x<sub>m</sub>) = 0 | ||
+ | |} | ||
+ | |||
+ | * f: R<sub>m</sub> → R<sub>m</sub> | ||
+ | * f_ = (f<sub>1</sub>, …, f<sub>m</sub>)<sup>T</sup> | ||
+ | * x_ = (x<sub>1</sub>, …, x<sub>m</sub>)<sup>T</sup> | ||
+ | * f_ (x_) = 0 | ||
+ | |||
+ | === Методы === | ||
+ | ==== Самый простой метод ==== | ||
+ | Пусть корень вещественный. Тогда самый простой метод — разбить отрезок на несколько. Тогда если знак на каком-то из отрезков меняется, то на нём есть нечётное число корней, и его можно разбить ещё. Если же знак не меняется, то там либо нет корней, либо чётное их количество. | ||
+ | |||
+ | ==== Метод бисекции ==== | ||
+ | Второй метод более регулярный и он называется метод бисекции. | ||
+ | * f(a) < 0 | ||
+ | * f(b) > 0 | ||
+ | * Берётся x<sub>0</sub> = (a + b)/2 | ||
+ | * Если f(x<sub>0</sub>) > 0, то x<sub>*</sub> ∈ (a, x<sub>0</sub>) | ||
+ | Каждый раз мы сужаем в два раза промежуток, где находится корень | ||
+ | |||
+ | === Начальное приближение === | ||
+ | Ведём понятие окрестности корня: | ||
+ | * U<sub>a</sub>(x<sub>*</sub>) = {x: |x − x<sub>*</sub>| < a} | ||
+ | |||
+ | Начальное приближение будем брать в окрестности корня | ||
+ | |||
+ | == Параграф 2. Метод простой итерации (МПИ) == | ||
+ | * f(x) = 0 (1) | ||
+ | * x<sub>*</sub> ∈ U<sub>a</sub>(x<sub>*</sub>) (по определению) | ||
+ | * x = S(x) (2) | ||
+ | * x<sub>n + 1</sub> = S(x<sub>n</sub>) (3) | ||
+ | * x<sub>0</sub> ∈(x<sub>*</sub>) | ||
+ | |||
+ | S(x) выбирается следующим образом: S(x) = x + r(x)f(x) (4). Единственное требование на r(x): sign(r(x)) ≠ 0 при x ∈ U<sub>a</sub>(x<sub>*</sub>). | ||
+ | |||
+ | Говорят, что S(x)Липшиц-непрерывна (удовлетворпяет условию Лиешица с константой q), x ∈ U<sub>a</sub>(x<sub>*</sub>), ∀ x<sub>1</sub>, x<sub>2</sub> ∈ U<sub>a</sub>(x<sub>*</sub>): |S(x<sub>1</sub>) − S(x<sub>2</sub>)| ≤ q|x<sub>1</sub> − x<sub>2</sub>| | ||
+ | |||
+ | Это условие сильнее непрерывности и слабее дифференцируемости. | ||
+ | |||
+ | '''Утверждение'''. Пусть S(x) — Липшиц-непрерывна с 0 < q < 1. Тогда МПИ сходится для ∀ x<sub>0</sub> ∈ U<sub>a</sub>(x<sub>*</sub>) со скоростью геометрической функции. | ||
+ | |||
+ | '''Доказательство'''. Методом матиндукции | ||
+ | * |x<sub>0</sub> − x<sub>*</sub>| < a | ||
+ | * |x<sub>n</sub> − x<sub>*</sub>| < a | ||
+ | * |x<sub>n + 1</sub> − x<sub>*</sub>| < q|x<sub>n</sub> − x<sub>*</sub>| | ||
+ | ** |x<sub>n + 1</sub> − x<sub>*</sub>| = |S(x<sub>n</sub>) − S(x<sub>*</sub>)| < q|x<sub>n</sub> − x<sub>*</sub>| | ||
+ | Понятно, что эту формулу можно трактовать как рекуррентную, и тогда | ||
+ | * |x<sub>n</sub> − x<sub>*</sub>| < q<sup>n</sup>|x<sub>0</sub> − x<sub>*</sub>| | ||
+ | * lim<sub>n → ∞</sub>q<sup>n</sup> = 0 ⇒ x<sub>n</sub> → x<sub>*</sub> | ||
+ | |||
+ | '''Замечание 1'''. Если известно, что ∃ S'(x), и sup<sub>x ∈ U<sub>a</sub>(x<sub>*</sub>)</sub> |S'(x)| = q < 1, то МПИ сходится, x<sub>0</sub> ∈ U<sub>a</sub>(x<sub>*</sub>) | ||
+ | |||
+ | '''Замечание 2'''. Расмотрим МПИ, записанный следующим образом: | ||
+ | * (x<sub>n + 1</sub> − x<sub>n</sub>)/τ + f(x<sub>n</sub>) = 0, τ > 0, x<sub>0</sub> ∈ U<sub>a</sub>(x<sub>*</sub>), n = 0, 1, 2, … (5) | ||
+ | * ∃ f'(x), M<sub>1</sub> = sup<sub>x ∈ U<sub>a</sub>(x<sub>*</sub>)</sub> |f'(x)| | ||
+ | * S(x) = x − τf(x) | ||
+ | * Продифференцируем: S'(x) = 1 − τf'(x). Если модуль |S'(x)| < 1, то МПИ сходится. Найдём условия на τ: | ||
+ | ** −1 < 1 − τf'(x) < 1 ⇒ 0 < τ < 2/M<sub>1</sub> | ||
+ | Так что если в итерационном методе (5) будем выбирать τ в границах, указанных выше, то получим сходимость со скоростью геометрической прогрессии. | ||
+ | |||
+ | <!-- Педедыв --> | ||
+ | |||
+ | === Метод Эйткена ускоренной сходимости === | ||
+ | Предположим, что x<sub>n</sub> − x<sub>*</sub> = Aq<sup>n</sup> (6). Запишем три итерации: | ||
+ | * x<sub>n − 1</sub> − x<sub>*</sub> = Aq<sup>n − 1</sup> (7) | ||
+ | * x<sub>n</sub> − x<sub>*</sub> = Aq<sup>n</sup> (8) | ||
+ | * x<sub>n + 1</sub> − x<sub>*</sub> = Aq<sup>n +1</sup> (9) | ||
+ | Тогда: | ||
+ | * x<sub>n + 1</sub> = x<sub>*</sub> + Aq<sup>n + 1</sup> | ||
+ | * x<sub>*</sub> = x<sub>n + 1</sub> − Aq<sup>n + 1</sup> | ||
+ | * (x<sub>n + 1</sub> − x<sub>n</sub>)<sup>2</sup> = A<sup>2</sup>q<sup>2n</sup>(q − 1)<sup>2</sup> | ||
+ | * x<sub>n + 1</sub> − 2x<sub>n</sub> + x<sub>n − 1</sub> = Aq<sup>n − 1</sup>(q − 1)<sup>2</sup> | ||
+ | * ((x<sub>n + 1</sub> − x<sub>n</sub>)<sup>2</sup>)/(x<sub>n + 1</sub> − 2x<sub>n</sub> + x<sub>n − 1</sub>) = Aq<sup>n − 1</sup> | ||
+ | * x<sub>*</sub> = x<sub>n</sub> − ((x<sub>n + 1</sub> − x<sub>n</sub>)<sup>2</sup>)/(x<sub>n + 1</sub> − 2x<sub>n</sub> + x<sub>n − 1</sub>) | ||
+ | Но так как (6) неточно, то это оказывается хоть и достаточно точным, но приближением. | ||
+ | |||
+ | '''Замечание'''. Неважно, какой метод мы ускоряем, главное, чтобы он был записан в виде (6). | ||
+ | |||
+ | == Параграф 3. Метод Ньютона (касательных) и метод секущих == | ||
+ | |||
+ | Нас неудовлетворяет метод простой итерации, медленная сходимость. | ||
+ | |||
+ | * f(x) = 0 (1) | ||
+ | * x<sub>*</sub> ∈ U<sub>a</sub>(x<sub>*</sub>) (по определению) | ||
+ | * x<sup>n</sup> — n-я итерация | ||
+ | * x<sup>n + 1</sup> = x<sup>n</sup> − f(x<sup>n</sup>)/f'(x<sup>n</sup>), n = 0, 1, …, x<sup>0</sup> — начальное приближение (2) | ||
+ | * От функции требуется гладкость до третьей производной | ||
+ | |||
+ | Метод Ньютона очень быстро сходится, но он может зацикливаться. | ||
+ | |||
+ | Модифицированный метод Ньютона: | ||
+ | * x<sup>n + 1</sup> = x<sup>n</sup> − f(x<sup>n</sup>)/f'(x<sup>0</sup>), n = 0, 1, …, x<sup>0</sup> — начальная итерация | ||
+ | * Скорость сходимости колеблется, но производительность повышается (особенно в системах) и позволяет избежать зацикливания | ||
+ | |||
+ | === Вывод метода Ньютона === | ||
+ | * 0 = f(<sub>*</sub>) = f(x) + (x<sub>*</sub> − x)f'(x) | ||
+ | * x→ x<sup>n</sup> | ||
+ | * x<sub>*</sub> → x<sup>n + 1</sup> | ||
+ | * f(x<sup>n</sup>) + (x<sup>n + 1</sup> − x<sup>n</sup>)f'(x<sup>n</sup>) = 0 | ||
+ | * x<sup>n + 1</sup> = x<sup>n</sup> − f(x<sup>n</sup>)/f'(x<sup>n</sup>) | ||
+ | |||
+ | Начальное приближение выбираем очень и очень жёстко. | ||
+ | |||
+ | === Вывод метода Ньютона для системы уравнений === | ||
+ | ==== Частный случай для двух уравнений ==== | ||
+ | {| | ||
+ | |rowspan= "2"|{ | ||
+ | |f<sub>1</sub>(x<sub>1</sub>, x<sub>2</sub>) = 0 | ||
+ | |rowspan="2"| (3) | ||
+ | |- | ||
+ | |f<sub>2</sub>(x<sub>1</sub>, x<sub>2</sub>) = 0 | ||
+ | |} | ||
+ | |||
+ | (x<sub>1</sub><sup>*</sup>, x<sub>2</sub><sup>*</sup>) — решение | ||
+ | * 0 = f<sub>1</sub>(x<sub>1</sub><sup>*</sup>, x<sub>2</sub><sup>*</sup>) = f(x<sub>1</sub>, x<sub>2</sub>) + (x<sub>1</sub><sup>*</sup> − x<sub>1</sub>) (δf<sub>1</sub>/δx<sub>1</sub>)(x<sub>1</sub>, x<sub>2</sub>) + (x<sub>2</sub><sup>*</sup> − x<sub>2</sub>) (δf<sub>2</sub>/δx<sub>2</sub>)(x<sub>1</sub>, x<sub>2</sub>) | ||
+ | * x<sub>i</sub> → x<sub>i</sub><sup>n</sup> | ||
+ | * x<sub>i</sub><sup>*</sup> → x<sub>i</sub><sup>n + 1</sup> | ||
+ | |||
+ | {| | ||
+ | |rowspan= "2"|{ | ||
+ | |f<sub>1</sub>(x<sub>1</sub><sup>n</sup>, x<sub>2</sub><sup>n</sup>) + (x<sub>1</sub><sup>n + 1</sup> − x<sub>1</sub><sup>n</sup>) (δf<sub>1</sub>/δx<sub>1</sub>)(x<sub>1</sub><sup>n</sup>, x<sub>2</sub><sup>n</sup>) + (x<sub>2</sub><sup>n + 1</sup> − x<sub>2</sub><sup>n</sup>) (δf<sub>1</sub>/δx<sub>2</sub>)(x<sub>1</sub><sup>n</sup>, x<sub>2</sub><sup>n</sup>) = 0 | ||
+ | |rowspan= "2"| (4) | ||
+ | |- | ||
+ | |f<sub>2</sub>(x<sub>1</sub><sup>n</sup>, x<sub>2</sub><sup>n</sup>) + (x<sub>1</sub><sup>n + 1</sup> − x<sub>1</sub><sup>n</sup>) (δf<sub>2</sub>/δx<sub>1</sub>)(x<sub>1</sub><sup>n</sup>, x<sub>2</sub><sup>n</sup>) + (x<sub>2</sub><sup>n + 1</sup> − x<sub>2</sub><sup>n</sup>) (δf<sub>2</sub>/δx<sub>2</sub>)(x<sub>1</sub><sup>n</sup>, x<sub>2</sub><sup>n</sup>) = 0 | ||
+ | |} | ||
+ | |||
+ | {| | ||
+ | |rowspan= "2"|J(x) = ( | ||
+ | |(δf<sub>1</sub>/δx<sub>1</sub>)(x<sub>1</sub><sup>n</sup>, x<sub>2</sub><sup>n</sup>) | ||
+ | |(δf<sub>1</sub>/δx<sub>2</sub>)(x<sub>1</sub><sup>n</sup>, x<sub>2</sub><sup>n</sup>) | ||
+ | |rowspan= "2"|) | ||
+ | |- | ||
+ | |(δf<sub>2</sub>/δx<sub>1</sub>)(x<sub>1</sub><sup>n</sup>, x<sub>2</sub><sup>n</sup>) | ||
+ | |(δf<sub>2</sub>/δx<sub>2</sub>)(x<sub>1</sub><sup>n</sup>, x<sub>2</sub><sup>n</sup>) | ||
+ | |} | ||
+ | |||
+ | * f = (f<sub>1</sub>, f<sub>2</sub>)<sup>T</sup> | ||
+ | * x<sup>n</sup> = (x<sub>1</sub><sup>n</sup>, x<sub>2</sub><sup>n</sup>) | ||
+ | * f(x<sup>n</sup>) + J(x<sup>n</sup>)(x<sup>n + 1</sup> − x<sup>n</sup>) = 0 | ||
+ | * ∃ J<sup>−1</sup>(x<sup>n</sup>) | ||
+ | * x<sup>n + 1</sup> = x<sup>n</sup> − J<sup>−1</sup>(x<sup>n</sup>)f(x<sup>n</sup>), n = 0, 1, …, x<sup>0</sup> ∈ U<sub>a</sub>(x<sup>*</sup>) (5) | ||
+ | |||
+ | ==== Общий случай для m уравнений ==== | ||
+ | |||
+ | {| | ||
+ | |rowspan= "4"|{ | ||
+ | |f<sub>1</sub>(x<sub>1</sub>, x<sub>2</sub>, …, x<sub>m</sub>) = 0 | ||
+ | |rowspan="4"| (6) | ||
+ | |- | ||
+ | |f<sub>2</sub>(x<sub>1</sub>, x<sub>2</sub>, …, x<sub>m</sub>) = 0 | ||
+ | |- | ||
+ | |… | ||
+ | |- | ||
+ | |f<sub>m</sub>(x<sub>1</sub>, x<sub>2</sub>, …, x<sub>m</sub>) = 0 | ||
+ | |- | ||
+ | |} | ||
+ | |||
+ | * (J(x))<sub>ij</sub> = (δf<sub>i</sub>/δx<sub>j</sub>), i, j = 1…m | ||
+ | * x<sup>n + 1</sup> = x<sup>n</sup> − J<sup>−1</sup>(x<sup>n</sup>)f(x<sup>n</sup>), n = 0, 1, …, x<sup>0</sup> ∈ U<sub>a</sub>(x<sup>*</sup>) (6) | ||
+ | * x<sup>n + 1</sup> = x<sup>n</sup> − J(x<sup>0</sup>)f(x<sup>n</sup>) | ||
+ | |||
+ | === Метод секущей (хорд) === | ||
+ | |||
+ | * x<sup>n + 1</sup> = x<sup>n</sup> − f(x<sup>n</sup>)/f'(x<sup>0</sup>), n = 0, 1, … | ||
+ | * f'(x<sup>n</sup>) = (f(x<sup>n + 1</sup>) − f(x<sup>n</sup>))/(x<sup>n + 1</sup> − x<sup>n</sup>) | ||
+ | Подставим в метод Ньютона приближение производной: | ||
+ | * x<sup>n + 1</sup> = x<sup>n</sup> − (x<sup>n</sup> − x<sup>n − 1</sup>)f(x<sup>n</sup>)/(f(x<sup>n</sup>) − f(x<sup>n − 1</sup>)) | ||
+ | |||
+ | {{Численные Методы}} | ||
+ | {{Lection-stub}} |
Текущая версия
Предыдущая лекция | Следующая лекция
Содержание |
[править] Глава 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
Календарь
|
|
|
Дополнительная информация |
Материалы к экзамену |