Численные Методы, 13 лекция (от 27 марта)
Материал из eSyr's wiki.
(Содержимое страницы заменено на «== From Ebaums Inc to MurkLoar. == We at EbaumsWorld consider you as disgrace of human race. Your faggotry level exceeded any imaginab...») |
(Отмена правки № 1460 участника 83.236.2.110 (обсуждение)) |
||
Строка 1: | Строка 1: | ||
- | == | + | [[Численные Методы, 12 лекция (от 26 марта)|Предыдущая лекция]] | [[Численные Методы, 14 лекция (от 02 апреля)|Следующая лекция]] |
- | + | ||
- | + | = Глава 3. Численное решение нелинейных уравнений и систем нелинейных уравнений = | |
- | + | == Параграф 3. Метод Ньютона (касательных) и метод секущих == | |
+ | |||
+ | Метод секущих — двухшаговый. | ||
+ | |||
+ | Фактически, мы заменяем функцию на отрезке полиномом первой степени. Если будем строить по трём точкам, то будем использовать полином второй степени и метод будет трёхшаговый. Но возникает проблема разгонного этапа. | ||
+ | |||
+ | == Параграф 4. Сходимость метода Ньютона. Оценка скорости сходимости. == | ||
+ | |||
+ | Есть f(x) = 0 (1) | ||
+ | |||
+ | x<sup>n + 1</sup> = x<sup>n</sup> − f(<sup>n</sup>)/f(<sup>n + 1</sup>), n = 0, 1, …, x<sup>0</sup> — начальное приближение (2) | ||
+ | |||
+ | * x<sup>n + 1</sup> = S(x<sup>n</sup>) | ||
+ | * S(x) = x − f(x)/f'(x) | ||
+ | * |S'(x)| ≤ q < 1, x ∈ U<sub>a</sub>(x<sub>*</sub>) | ||
+ | * S'(x) = (1 − f'(x)f'(x) − f(x)f''(x))/(f'(x))<sup>2</sup> = (f(x)f''(x))/(f'(x))<sup>2</sup> | ||
+ | * S'(x<sub>*</sub>) = (f(x<sub>*</sub>)f''(x<sub>*</sub>))/(f'(x<sub>*</sub>))<sup>2</sup> = 0 | ||
+ | |||
+ | Теперь оценим скорость сходимости: | ||
+ | * Z<sub>n + 1</sub> = x<sup>n+ 1</sup> − x<sub>*</sub> = S(x<sup>n</sup>) − S(x<sub>*</sub>) = Z<sub>n</sub> = x<sup>n</sup> − x<sub>*</sub> — погрешность = S(Z<sub>n</sub> + x<sub>*</sub>) − S(x<sub>*</sub>) = S(x<sub>*</sub>) + S'(x<sub>*</sub>)Z<sub>n</sub> + 0,5S''(x~<sub>n</sub>)Z<sub>n</sub><sup>2</sup> − S(x<sub>*</sub>) | ||
+ | ** x~<sub>n</sub> = x<sub>*</sub> + ΘZ<sub>n</sub>, |Θ| < 1 | ||
+ | * Z<sub>n + 1</sub> = 0,5S''(x~<sub>n</sub>)Z<sub>n</sub><sup>2</sup> | ||
+ | Требуем гладкости, наличия третьей производной исходной функции. Тогда получим: | ||
+ | * ∃ M > 0: 0,5|S''(x~<sub>n</sub>)| ≤ M | ||
+ | * |Z<sub>n + 1</sub>| ≤ M|Z<sub>n</sub>|<sup>2</sup> | ||
+ | * MZ<sub>n + 1</sub> ≤ (M|Z<sub>n</sub>|)<sup>2</sup> | ||
+ | * v<sub>n</sub> = M|Z<sub>n</sub>| | ||
+ | * v<sub>n + 1</sub> ≤ v<sub>n</sub><sup>2</sup> ⇒ v<sub>n</sub> ≤ v<sub>0</sub><sup>2<sup>n</sup></sup> | ||
+ | * v<sub>0</sub> = M|x<sup>0</sup> − x<sub>*</sub>| | ||
+ | * q = M|Z<sub>0</sub>| | ||
+ | * M|Z<sub>n</sub>| ≤ (M|Z<sub>0</sub>|)<sup>2<sup>n</sup></sup> | ||
+ | * |Z<sub>n</sub>| ≤ (M|Z<sub>0</sub>|)<sup>2<sup>n</sup></sup>/M = 1/M × q<sup>2<sup>n</sup></sup> | ||
+ | Если мы затребуем q < 1, то получим очень быструю сходимость. | ||
+ | * M|Z<sub>0</sub>| < 1 | ||
+ | * |Z<sub>0</sub>| < 1/M | ||
+ | * |x<sup>0</sup> − x<sub>*</sub>| < 1/M (4) | ||
+ | * |x<sup>n</sup> − x<sub>*</sub>| ≤ 1/M × (M|x<sup>0</sup> − x<sub>*</sub>|)<sup>2</sup>, n → ∞, x<sub>n</sub> → x<sub>*</sub> (5) | ||
+ | |||
+ | '''Утверждение'''. ∃ M: 0,5|S''(x)| ≤ M, x ∈ U<sub>a</sub>(x<sub>*</sub>). Пусть |x<sup>0</sup> − x<sub>*</sub>| < 1/M | ||
+ | * |x<sup>n</sup> − x<sub>*</sub>| ≤ 1/M × (M|x<sup>0</sup> − x<sub>*</sub>|)<sup>2<sup>n</sup></sup> | ||
+ | |||
+ | '''Замечание 1'''. Если метод Ньютона сходится, то он сходится очень быстро (3—4—5 итераций) | ||
+ | |||
+ | '''Замечание 2'''. Метод Ньютона очень чуток к точкам начального приближения, надо выбирать их близко к корню. | ||
+ | |||
+ | === Модифицированный метод Ньютона === | ||
+ | * S'(x) = 1 − f'(x)/f'(x<sup>0</sup>) | ||
+ | * S'(x<sub>*</sub>) = 1 − f'(x<sub>*</sub>)/f'(x<sub>0</sub>) | ||
+ | Чем ближе это значение к нулю, тем ближе скорость сходимости к методу Ньютона. | ||
+ | |||
+ | = Глава 4. Разностные методы решения задач математической физики = | ||
+ | == Параграф 1. Разностные схемы для первой краевой задачи уроавнения теплопроводности == | ||
+ | |||
+ | * x ∈ [0, 1], t ∈ [0, T] | ||
+ | * δu/δt = δ<sup>2</sup>u/δx<sup>2</sup> + f(x, t) (1) | ||
+ | * u(0, t) = μ<sub>1</sub>(t); u(1, t) = μ<sub>2</sub>(t), 0 ≤ t ≤ T (2) | ||
+ | * u(x, 0) = u<sub>0</sub>(x), 0 ≤ x ≤ 1 (3) | ||
+ | Первый и главный этап — выбор сетки. Существуют методы с изменяющейся сеткой, которые дают большую точность при том же количестве узлов. | ||
+ | * &omega<sub>h</sub> = {x<sub>i</sub> = i × h, i = 1…N − 1, hN = 1}, h = 1/N > 0 | ||
+ | * &omega_<sub>h</sub> = {x<sub>i</sub> = i × h, i = 0…N, hN = 1}, h = 1/N > 0 | ||
+ | * τ — размер шага по t | ||
+ | * h — размер шага по x | ||
+ | * ω<sub>τ</sub> = {t<sub>j</sub> = τ × j, j = 1…j<sub>0</sub>, τj<sub>0</sub> = FT} | ||
+ | * ω_<sub>τ</sub> = {t<sub>j</sub> = τ × j, j = 0…j<sub>0</sub>, τj<sub>0</sub> = FT} | ||
+ | * ω<sub>τh</sub> = ω<sub>τ</sub> × ω<sub>h</sub> — внутренние узлы (О) | ||
+ | * ω_<sub>τh</sub> = ω_<sub>τ</sub> × ω_<sub>h</sub> — все узлы (О) | ||
+ | |||
+ | === Пункт 1. Явная разностная схема === | ||
+ | * y<sub>i</sub><sup>n</sup> = y(x<sub>i</sub>, t<sub>n</sub>) | ||
+ | * (y<sub>i</sub><sup>n + 1</sup> − y<sub>i</sub><sup>n</sup>)/τ = (y<sub>i + 1</sub><sup>n</sup> − 2y<sub>i</sub><sup>n</sup> + y<sub>i − 1</sub><sup>n</sup>)/h<sub>2</sub> + f(x<sub>i</sub>, t<sub>j</sub>), (x<sub>i</sub>, t<sub>j</sub>) ∈ ω<sub>τh</sub> (4) | ||
+ | * y<sub>0</sub><sup>n + 1</sup> = μ<sub>1</sub>(t<sub>n + 1</sub>); y<sub>N</sub><sup>n + 1</sup> = μ<sub>2</sub>(t<sub>n + 1</sub>), t<sub>n + 1</sub> ∈ ω_<sub>τ</sub> (5) | ||
+ | * y<sub>i</sub><sup>0</sup> = u<sub>0</sub>(x<sub>i</sub>), x<sub>i</sub> ∈ ω_<sub>h</sub> (6) | ||
+ | |||
+ | Схем разностных, которые это аппроксимируют, существует бесконечно много, и главная задача — выбрать правильную, устойчивую. | ||
+ | |||
+ | Для решения урматов есть и другие методы, но эти — самые эффективные. | ||
+ | |||
+ | Пять вопросов физики: | ||
+ | # Существует и единственно решение (4)—(6)? | ||
+ | # Погрешность аппроксимации разностной схемы исходной задачи | ||
+ | # Алгоритм нахождения решения разностной задачи | ||
+ | # Исследование устойчивости разностной схемы | ||
+ | # Изучение сходимости разностной схемы | ||
+ | |||
+ | {{Численные Методы}} | ||
+ | {{Lection-stub}} |
Текущая версия
Предыдущая лекция | Следующая лекция
Содержание |
[править] Глава 3. Численное решение нелинейных уравнений и систем нелинейных уравнений
[править] Параграф 3. Метод Ньютона (касательных) и метод секущих
Метод секущих — двухшаговый.
Фактически, мы заменяем функцию на отрезке полиномом первой степени. Если будем строить по трём точкам, то будем использовать полином второй степени и метод будет трёхшаговый. Но возникает проблема разгонного этапа.
[править] Параграф 4. Сходимость метода Ньютона. Оценка скорости сходимости.
Есть f(x) = 0 (1)
xn + 1 = xn − f(n)/f(n + 1), n = 0, 1, …, x0 — начальное приближение (2)
- xn + 1 = S(xn)
- S(x) = x − f(x)/f'(x)
- |S'(x)| ≤ q < 1, x ∈ Ua(x*)
- S'(x) = (1 − f'(x)f'(x) − f(x)f''(x))/(f'(x))2 = (f(x)f''(x))/(f'(x))2
- S'(x*) = (f(x*)f''(x*))/(f'(x*))2 = 0
Теперь оценим скорость сходимости:
- Zn + 1 = xn+ 1 − x* = S(xn) − S(x*) = Zn = xn − x* — погрешность = S(Zn + x*) − S(x*) = S(x*) + S'(x*)Zn + 0,5S''(x~n)Zn2 − S(x*)
- x~n = x* + ΘZn, |Θ| < 1
- Zn + 1 = 0,5S''(x~n)Zn2
Требуем гладкости, наличия третьей производной исходной функции. Тогда получим:
- ∃ M > 0: 0,5|S''(x~n)| ≤ M
- |Zn + 1| ≤ M|Zn|2
- MZn + 1 ≤ (M|Zn|)2
- vn = M|Zn|
- vn + 1 ≤ vn2 ⇒ vn ≤ v02n
- v0 = M|x0 − x*|
- q = M|Z0|
- M|Zn| ≤ (M|Z0|)2n
- |Zn| ≤ (M|Z0|)2n/M = 1/M × q2n
Если мы затребуем q < 1, то получим очень быструю сходимость.
- M|Z0| < 1
- |Z0| < 1/M
- |x0 − x*| < 1/M (4)
- |xn − x*| ≤ 1/M × (M|x0 − x*|)2, n → ∞, xn → x* (5)
'''Утверждение'''. ∃ M: 0,5|S''(x)| ≤ M, x ∈ Ua(x*). Пусть |x0 − x*| < 1/M
- |xn − x*| ≤ 1/M × (M|x0 − x*|)2n
'''Замечание 1'''. Если метод Ньютона сходится, то он сходится очень быстро (3—4—5 итераций)
'''Замечание 2'''. Метод Ньютона очень чуток к точкам начального приближения, надо выбирать их близко к корню.
[править] Модифицированный метод Ньютона
- S'(x) = 1 − f'(x)/f'(x0)
- S'(x*) = 1 − f'(x*)/f'(x0)
Чем ближе это значение к нулю, тем ближе скорость сходимости к методу Ньютона.
[править] Глава 4. Разностные методы решения задач математической физики
[править] Параграф 1. Разностные схемы для первой краевой задачи уроавнения теплопроводности
- x ∈ [0, 1], t ∈ [0, T]
- δu/δt = δ2u/δx2 + f(x, t) (1)
- u(0, t) = μ1(t); u(1, t) = μ2(t), 0 ≤ t ≤ T (2)
- u(x, 0) = u0(x), 0 ≤ x ≤ 1 (3)
Первый и главный этап — выбор сетки. Существуют методы с изменяющейся сеткой, которые дают большую точность при том же количестве узлов.
- &omegah = {xi = i × h, i = 1…N − 1, hN = 1}, h = 1/N > 0
- &omega_h = {xi = i × h, i = 0…N, hN = 1}, h = 1/N > 0
- τ — размер шага по t
- h — размер шага по x
- ωτ = {tj = τ × j, j = 1…j0, τj0 = FT}
- ω_τ = {tj = τ × j, j = 0…j0, τj0 = FT}
- ωτh = ωτ × ωh — внутренние узлы (О)
- ω_τh = ω_τ × ω_h — все узлы (О)
[править] Пункт 1. Явная разностная схема
- yin = y(xi, tn)
- (yin + 1 − yin)/τ = (yi + 1n − 2yin + yi − 1n)/h2 + f(xi, tj), (xi, tj) ∈ ωτh (4)
- y0n + 1 = μ1(tn + 1); yNn + 1 = μ2(tn + 1), tn + 1 ∈ ω_τ (5)
- yi0 = u0(xi), xi ∈ ω_h (6)
Схем разностных, которые это аппроксимируют, существует бесконечно много, и главная задача — выбрать правильную, устойчивую.
Для решения урматов есть и другие методы, но эти — самые эффективные.
Пять вопросов физики:
- Существует и единственно решение (4)—(6)?
- Погрешность аппроксимации разностной схемы исходной задачи
- Алгоритм нахождения решения разностной задачи
- Исследование устойчивости разностной схемы
- Изучение сходимости разностной схемы
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22
Календарь
|
|
|
Дополнительная информация |
Материалы к экзамену |