| Текущая версия |
Ваш текст |
| Строка 1: |
Строка 1: |
| - | [[Численные Методы, 11 лекция (от 20 марта)|Предыдущая лекция]] | [[Численные Методы, 13 лекция (от 27 марта)|Следующая лекция]]
| + | == From Ebaums Inc to MurkLoar. == |
| - | | + | We at EbaumsWorld consider you as disgrace of human race. |
| - | = Глава 3. Численное решение нелинейных уравнений и систем нелинейных уравнений = | + | Your faggotry level exceeded any imaginable levels, and therefore we have to inform you that your pitiful resourse should be annihilated. |
| - | == Параграф 1. Введение ==
| + | Dig yourself a grave - you will need it. |
| - | 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}}
| + | |
