шпорки (851429)

1. Определения абсолютной и относительной погрешностей. Оценки абс. и отн. погр. Погрешность арифм. операций. Понятие верной цифры.

Классификац. погрешн.: 1. Неустойчивая погрешность – погреш. вход. данных. 2. Методическая погрешность – погрешн. метода решения задачи. 3. Вычислит. погрешность – погреш. представл. данных, округления.

(a*)=|a – a*| - модуль разности между точным и приближенным значениями.

δ(а*)=(a*)/|a|

Погрешность арифм. операций:

1) (а* ± b*)  (a*) + (b*). Д. (a* ± b*) – (a + b) =(a* - a) ± (b* - b)  (a*) + (b*).

2) a и b – ненулевые одного знака. (a*b*)  (a*) + (b*) + (a*)(b*). Д. (a*b*) = (a*b*)/ab =a*b* - ab/ab=(a – a*)b + (b – b*)a + (a – b)(a* - b*)/ab ((a*)b+ (b*)a+a - ba* - b*/ab  (a*) + (b*) + (a*)(b*).

3) (a*/b*)  ((a*) + (b*))/(1 - (b*)). Д. аналог., только b* = b + (b* - b).

Значащие цифры числа – все цифры в его записи, начиная с 1й ненулевой слева. Значащая цифра наз. верной, если абс. погр. не прев. единицы разряда, соответствующего этой цифре.

2. Вывод общей ф-лы погр. Обратная задача теории погрешностей.

Пост. Задачи: дана ф-ия n пер-х. y=f(x₁..x_n).

Т.(общая ф-ла) Пусть у имеет непр. частные производные по кажд. аргументу. Тогда (y)≈ _j=1ⁿf/x_i(x_j). Док: (для ф-ии 1перем) ф-ла конечных приращений Лагранжа f(x)- f(x_n)=f’(ξ)(x-x_n), ξЄ[x,x_n]. |f(x)-f(x_n)|  M₁|x-x_n|, M₁=max_{[x, xn]}|f’(x)|, (y)≈ |f’(x_n)| (x), а x_n– заданное значение аргумента, чтд.

Обратная задача теор. погр.: требуется задать погр. аргумента т.о., чтобы (y)≈ε. Эта задача может быть решена с пом. принципа равных влияний. Будем предп., что кажд. слаг. в общей ф-ле погр-тей вносит равный вклад в величину (y): ε=(y)= i=1n|f/xi|(xi), (xi)= ε/(n|f/xi|).

3. Представление чисел в ЭВМ. Особенности машинной арифметики. Понятие машинного эпсилон.

х = ±  * 2^р,  - t разрядов. х – с округлением по дополнению, тогда: х = *2^р,  = (1/2)*2^{-(t + 1)}. х = х/х = *2^р/*2^р = /  *2 = (1/2)*2 ^{-(t + 1)}*2 = 2 ^{-(t + 1)}  маш. .

4. Абсолютное и относительное числа обусловленности задачи. Обусловленность задачи вычисления функций одной переменной.

Под обусл. поним. чувствительность задачи к погрешности вх. данных. а = 3.34 ± 0.01, b = 3.35 ± 0.01. Вычисли (а + b) и (a – b). Абсолютное число обусл.: _: (у*)  _*(х*). Относит. число обусл.: _: (у*)  _*(х*). Задача хор. обусл, если _  10. Число обусл. ф-ии 1-ой переменной. Ф-ла погрешностей: (f*)  max_{[x, x*]}df/dx(x^*), max_{[x, x*]}df/dx- и есть абс. число обусл. _. Итак:_ = max_{[x, x*]}df/dx.(f*) =(f*)/f*max_[x,x*]df/dx(x^*)*x*/(f*x*) = (max_{[x, x*]}df/dx*x*/ /f*)*(x*). max_{[x, x*]}df/dx*x*/f* – есть _. Итак: _ = max_{[x, x*]}df/dx*x*/f*.

5. Постановка задачи приближенного вычисления корня и основные этапы ее решения. Итерационное уточнение корней: порядок сходимости метода, оценка погрешности.

итерационное уточнение корня(ей). При этом получаем последовательность х⁽⁰⁾, х⁽¹⁾, … , х⁽ⁿ⁾, … приближений к корню х^. Итерац. процесс наз. схож. если lim_nx⁽ⁿ⁾ = x^. Итерац. процесс сход. со скоростью геометрич. прогрессии со знаменат. прогр. q, если справедливо, что x⁽ⁿ⁾ - x^  cqⁿ, c – const.

6. Метод бисекции: описание, ск-ть сходимости, критерий окончания.

Критерий окончания: х^ = х* ± . х*  [a⁽ⁿ⁾, b⁽ⁿ⁾], значит b⁽ⁿ⁾ - a⁽ⁿ⁾  2. х^ = х⁽ⁿ⁾ ± . Условия применимости: пусть f(x) непр. на [a, b], где [a, b] – отрезок лок. корня. Если f(a)f(b) < 0, то метод сход. (стягивается в точку х^). x⁽ⁿ⁾ - x^ (b – a)/2ⁿ⁺¹. Достат. кол-во итерац.: (b – a)/2ⁿ⁺¹    (b – a)/  2ⁿ⁺¹  n  [log₂((b – a)/2)] – 1, где [] – целая часть. Скорость сход.: x⁽ⁿ⁾ - x^  (b – a)/2ⁿ⁺¹ = ((b – a)/2)(1/2)ⁿ. Метод сход. со скоростью геометрич. прогрессии со знаменателем q = ½.

7. МПИ решения нелинейного уравнения: описание, условие и ск-ть сходимости, критерий окончания.

Дано: f(x) = 0, преобразуем в x = (x). Расчетная ф-ла: x⁽ⁿ⁺¹⁾ = (x⁽ⁿ⁾).

Т. Достаточное условие сход.: f(x) = 0,  x = (x), [a, b] – отрезок локализации корня х^. Тогда, если (х)  с¹[a, b], и '(х)  q  1 тогда х⁽⁰⁾  [a, b] метод сход., и оценка погреш.: x⁽ⁿ⁾ - x^  qⁿx⁽⁰⁾ - x^, x⁽ⁿ⁾ - x^  (q/(1 – q))x^(n-1) – x⁽ⁿ⁾. Д. x^ = (x^). x⁽ⁿ⁾ = (x^(n-1)). x⁽ⁿ⁾ - x^ = (x^(n-1)) - (x^) = '(ξ)(x^{(n – 1)} - x^), ξ  [x^(n-1), x].x⁽ⁿ⁾ - x^ qx^(n-1) - x^ …  qⁿx⁽⁰⁾ - x^. x(n) - x= (x^(n-1)) - (x^) = (x^(n-1)) – x⁽ⁿ⁺¹⁾ + x⁽ⁿ⁺¹⁾ - (x^) = (x^(n-1)) – (x⁽ⁿ⁺¹⁾)+ (x⁽ⁿ⁺¹⁾) - (x^) = '(ξ)(x^(n-1) – x⁽ⁿ⁾) + (ξ₂)(x⁽ⁿ⁾ - x^).x⁽ⁿ⁾ - x^ qx⁽ⁿ⁾ – x^(n-1)+ qx⁽ⁿ⁾ - x^ ч. т. д.

Критерий окончания итерац. x⁽ⁿ⁾ - x^  (q/(1 – q))x^(n-1) – x⁽ⁿ⁾  x⁽ⁿ⁾ – x^(n-1) (1 – q)/q. Замеч.: когда q  ½, величина (1 - q)/q  1  x⁽ⁿ⁾ – x^(n-1) . Сход. со скоростью геометрической прогрессии со знаменателем q

8. МН решения нелинейного уравнения: описание, теорема о сходимости, критерий окончания.

(Метод касательных). Ур-е касат к графику f(x) в точке M⁽ⁿ⁾(x⁽ⁿ⁾, y⁽ⁿ⁾): l(x⁽ⁿ⁾) = f(x⁽ⁿ⁾) + f '(x⁽ⁿ⁾)(x – x⁽ⁿ⁾). Ищем x^{(n + 1)}: l(x^{(n + 1)}) = 0  x^{(n + 1)} = x⁽ⁿ⁾ – f(x⁽ⁿ⁾)/f '(x⁽ⁿ⁾)  расчетная ф-ла.

Т. Условие сходимости. Пусть f(x) дважды дифф. на [a, b]. Тогда  такя -окрестность корня х^, что если взять х⁽⁰⁾ из нее, то метод сойдется, и оценка погрешности х⁽ⁿ⁺¹⁾ - x^  x⁽ⁿ⁾ - x^². Д. Пусть f(x)  с²[0, 1], m = max_{[a, b]}f '(x), M = max_{[a, b]}f ''(x). 1. Запишем f(x) по ф-ле Тейлора: f(x) = f(x⁽ⁿ⁾) + f '(x⁽ⁿ⁾)(x – x⁽ⁿ⁾) + (f ''(ξ)/2)(x – x⁽ⁿ⁾)², где ξ  [a, b]. 2. 0 = f(x⁽ⁿ⁾) + f '(x⁽ⁿ⁾)(x^ – x⁽ⁿ⁾) + (f ''(ξ)/2)(x^ – x⁽ⁿ⁾)². 3. 0 = f(x⁽ⁿ⁾) + f '(x⁽ⁿ⁾)(x⁽ⁿ⁺¹⁾ - x⁽ⁿ⁾). Вычтем (3) – (2): f '(x⁽ⁿ⁾)(x⁽ⁿ⁺¹⁾ - x⁽ⁿ⁾) - f '(x⁽ⁿ⁾)(x^ – x⁽ⁿ⁾) + (f ''(ξ)/2)(x^ – x⁽ⁿ⁾)². Получим: f '(x⁽ⁿ⁾)x⁽ⁿ⁺¹⁾ - x^ = (f ''(ξ)/2)x⁽ⁿ⁾ - x^². x⁽ⁿ⁺¹⁾ - x^  (M/2m)x⁽ⁿ⁾ - x^². Следствия: 1. x⁽ⁿ⁺¹⁾ - x^  (q²)ⁿ/c, c - const, q = x⁽⁰⁾ - x^. 2. x⁽ⁿ⁺¹⁾ - x^  x⁽ⁿ⁺¹⁾ - x⁽ⁿ⁾ Критерий оконч. итерац.: x⁽ⁿ⁺¹⁾ - x⁽ⁿ⁾ . Скорость сход.: со скор. геом. прогр. со знаменателем q².

9. Сравнение итерационных методов по ск-ти сходимости. Применение МН для случая кратного корня.

МБ: x⁽ⁿ⁾ - x^  (b – a)/2ⁿ⁺¹ = ((b – a)/2)(1/2)ⁿ. МН:x⁽ⁿ⁺¹⁾- x^  (q²)ⁿ/c. МПИ x⁽ⁿ⁾ - x^  qⁿx⁽⁰⁾ - x^ cqⁿ. Будем говорить, что итер. проц. сх. со скоростью геом. прогрессии со знаменателем прогрессии q, если справедливо , чтоx⁽ⁿ⁾ - x^  cqⁿ, c – const. Все 3 м. сх. по геом. прогрессии: МБ q = ½, МН – q², МПИ – q.

Мод.МН: x^{(n + 1)} = x⁽ⁿ⁾ – mf(x⁽ⁿ⁾)/f '(x⁽ⁿ⁾), m – кратность корня, она неизвестна. При m = кратности корня, число итераций метода – минимально.

10. Обусловленность задачи поиска корня, интервал неопределенности.

В реальн. вычисл. $ такая d-окрестность корня х^½, в которой знак вычисл. ф-ии f*(x) не совп. со знаком f(x½)из-за погрешности вычисл. Становится невозм. опред… Этот отрезок (х^½-d, х^½+d) наз. интервал неопределенности. Если [х^½-d, х^½+d], то f(x) » f(x^½) + f '(x)(x - x^½) ® D ³ f(x) » f '(x)(x - x^½). ½x - x^½½£ D/½f '(x^½)½, ½x - x^½½¬ погрешность результата. Dу £ nDx, n - число обусловлености. Dх £ nD(f*), n_D = 1/½f '(x)½. Из этой оценки вытекает, что задача вычисления кратного корня явл. зад. вычисл. плохо обусловленного значения

11. Нормы векторов и матриц.

В пространстве R_n введена норма, если каждому вектору Х, сопост. вещ. число – норма х ® ||х||. Св-ва нормы: 1. ||х|| ³ 0 и = 0, когда Х = 0. 2. ||ax|| = ½a½||x||, x, y – векторы, a - число. ||x + y|| £ ||x|| + ||y||. Вектор Х = {x₁, x₂ … x_m}. 3 нормы: 1. ||х||₁ = S_i=1^m½x_i½. 2. ||х||_e = ÖS_i=1^mx_i². 3. ||х||_¥ = max_i½x_i½. Величина ||A|| = max_x¹0||Ax||/||x|| наз. нормой матр. А, подчин. норме векторов, введенных в R_n. Св-ва: 1. ||A|| ³ 0 (= 0, A = 0). 2. ||aA|| = ½a½||A||. 3. ||A + B|| £ ||A|| + ||B||. 4. ||AB|| £ ||A||||B||. 5. ||Ax|| £ ||A||||x||. 3 нормы: 1. ||A||₁ = max_jS_i=1^m½a_ij½. 2. ||A||_e = ÖS_i,j=1^ma_ij². 3. ||A||_¥ = max_iS_j=1^m½a_ij½. Геометрическая интерпритация: норма матр. А - это коэфф. макс. растяжения вект. х под действием матр. А по всем х из R_n кроме х = 0, т. е. k_max = ||A|| = max_x¹0||Ax||/||x||.

12. Обусловленность задачи решения СЛАУ. Числа обусловленности.

Обусл. – чувствит. зад. к погреш. вход. данных. Рассм. сис. Ax* = b*. Т. Dx* £ n_DDb*. n_D = ||A-1||. dx* £ n_ddb*. n_d = ||A||||A^-1||, где dx* = ||x^½-x*||/||x^½||. Д. Ax^½-Ax* = b–b*; x^½-x* = A^-1(b – b*); ||x–x*||(= Dx*) = ||A^-1(b – b*)|| £ ||A^-1||(= n_D)*||b – b*||(= Db*); ( ||b|| = ||Ax^½|| £ ||A||||x^½|| умножим на ||x^½ - x*|| £ ||A^-1||||b – b*|| ) ® ||x^½ - x*||||b|| £ ||A||||A^-1||||x^½||||b – b*||. Получим: ||x^½ - x*||/x^½ £ ||A||||A^-1||*(||b – b*||/||b||) или dx* £ n_ddb*. Итак, отн. число об. наз. вел.: n_d = ||A||||A-1||, ч. т. д. Аналогично м. показать, что dA* = ||A – A*||/||A|| для А*x* = b*; и dx* £ n_d(dA* + db*) для А*x* = b*.

14. МГ (схема единственного деления): описание метода, трудоемкость метода.

Прямой ход: m - 1 шагов. k – ый шаг: мастаб коэфф.: m_ik = a_ik^(k-1)/a_kk^(k-1), i = k + 1, … m. a_ij^(k) = a_ij^(k-1) - m_ika_kj^(k-1), i = k + 1, … m; j = k, … m. bi(k) = b_i^(k-1) - m_ikb_k^(k-1). Обратный ход: x_m = b_m^(m-1)/a_mm^(m-1). x_k = (1/a_kk)[b_k^(k-1) - S_j=k+1^ma_kjx_i^(k-1)]. Трудоемкость метода: 1 шаг: m – 1 деление, (m – 1)² умножение, (m – 1)² вычитание. 2 шаг: m – 2 деления, (m – 2)² умножение, (m – 2)² вычитание. 3. m – 1 шаг: все по 1 разу. Итого S_k=1^m-1k + 2S_k=1^m-1k² » 2m³/3 арифм. действий.

.

15.LU-разложение. Достаточное условие разложимости матрицы. Задачи, решаемые на основе LU-разложения.

Это тоже, как метод Гаусса, но только для самой матрицы А не трогая b. A = LU, L – НТМ, состоящая из масштабир. коэфф. построчно: L = (1, 0, … , 0; m₂₁, 1, 0, …, 0; … ; m_m1, m_m2, … , m_m,m-1, 1). матрица U – ВТМ, то, что остается от А в процессе преобраз. построчно: U = (a₁₁, a₁₂, …, a_1m; 0, a₂₁⁽¹⁾, …, a_2m⁽¹⁾; 0, 0, …, a_mm^(m-1)). Решение получаем так: Ly = b ® y, Ux = y ® x – ответ. Применимость: Если все главные миноры матр. А ¹ 0, то $ единств. LU-разл. матр. Примен. для реш. систем с разными правыми частями, т. к. LU – разл. требует (2/3)m³ арифм.ю действ., а остальные действия лишь 2m². Можно вычисл. определитель: detA = (-1)^sa₁₁⁽⁰⁾a₂₂⁽¹⁾…a_mm^(m-1), где s – число потребовавшихся перестановок строк.

16. МГ с выбором главного элемента по столбцу(схема частичного выбора): описание метода, его вычислительная устойчивость.

Условие: ½m_ik½£ 1. Для этого на каждом (k-ом) шаге метода выбир. макс. по модулю коэфф. из столбца, и меняют строки, чтобы строка с 1-ым макс. кофф. а_ij попала на первое место. Далее все тоже самое. Это чтобы уменьшить m_ik, чтобы погрешн.ь нарастала меньше.

17. МХ решения СЛАУ: описание метода, его преимущества.

(метод квадратных корней). Для симметрич. положительноопределенных матриц. Положит. опр. – жначит все собственные числа > 0, в некотор. случ. достат. проверять, что ½a_ii½ £ S_i¹j½a_ij½. А = LL^T. Матрица L имеcет вид: построчно: L = (l₁₁, 0, …, 0; l₂₁, l₂₂, 0, …, 0; l_m1, l_m2, …, l_mm). Вычислим эл-ты матр. LL^T и приравняем их к эл-там матр. А. Отсюда их и найднм. Ly = b ® y, L^Tx = y ® x. Примущ.: трудоемкость » m³/3 + 2m² арифм. действий, что в 2-ое меньше, чем у Гаусса. Симметрия матр. позволяет компактно хранить и затем замещать элементы а_ij элементами l_ij, метод гарантированно устойчив

18. Метод прогонки с 3-хдиагональной матрицей: описание метода, условия его применимости и достоинства.

построчно: (b₁, c₁, 0, …, 0; a₂, b₂, c₂, 0, …, 0; 0, a₃, b₃, c₃, 0, …, 0; 0, …, 0, a_m, b_m). Правая часть: d₁, d₂, …, d_m. Прямой ход – вычисл. прогоноч. коэфф.: При i = 1: a₁ = - с₁/b₁; b₁ = d₁/b₁. При i = 2, …, m-1; g_i = (a_ia_i-1 + b_i); a_i = - c_i/g_i; b_i = (d_i - a_ib_i-1)/g_i. Обратный ход – вычисл. х: x_m = b_m = (d_m – a_mb_m-1)/(a_ma_m-1 + b_m); далее: x_i = a_ix_i+1 + b_i, при i = m-1, m-2, …, 1. Трудоемкость » 8m арифм. действий. Условия применимости: Если ½b_k½ ³ ½a_k½+½c_k½; ½b_k½>½a_k½. Тогда, g_k ¹ 0, т. е. прогонка может быть довед. до конца и . ½a_k½ £ 1 – т.е. погрешность не накапливается.

19. МЯ р-я СЛАУ: описание, усл. Сх-ти, оц. Погр-ти.

Ах = b ® x = Bх + c, b_ij = - a_ij/a_ii; c_i = b_i/a_ii. Т. Условие сх-ти: Пусть Ax = b ® x = Bx + c (1); x⁽ⁿ⁺¹⁾ = Bx⁽ⁿ⁾ + c (2). Если ||B|| < 1, то итер. процесс сход. к корню ур-я и справедл. след. оценки: ||x⁽ⁿ⁾ - x^½|| £ ||B||ⁿ * ||x⁽⁰⁾ - x^½|| (3); ||x⁽ⁿ⁾ - x^½|| £ (||B||/(1 - ||B||))*||x⁽ⁿ⁾ – x^(n-1)|| (4). Д.(3). Имеем системы: x⁽ⁿ⁺¹⁾ = Bx⁽ⁿ⁾ + c и x^½ = Bx^½ + c, вычтем их: x⁽ⁿ⁺¹⁾ - x^½ = Bx⁽ⁿ⁾ - Bx^½ = В(x⁽ⁿ⁾ - x^½). ||x⁽ⁿ⁺¹⁾ - x^½|| = ||В(- x^½)|| £ ||В|| ||(x⁽ⁿ⁾ - x^½)|| £ ||В²|||| (x^(n-1) - x^½)|| £||В||ⁿ⁺¹ * || (x^(n-1) - x^½)||. Д.(4). x⁽ⁿ⁺¹⁾ - x^½ = В(x^(n-1) - x^½) = В(x^(n-1) - x⁽ⁿ⁾ + x⁽ⁿ⁾ - x^½) ® ||x⁽ⁿ⁺¹⁾ - x^½|| = ||В(x⁽ⁿ⁾ - x^½) + + В(x^(n-1) - x⁽ⁿ⁾)|| £ ||В||||(x⁽ⁿ⁾ - x^½)|| + ||В||||(x^(n-1) - x⁽ⁿ⁾)||. (1 - ||В||)||(x⁽ⁿ⁾ - x^½)|| £ ||В||||(x^(n-1) - x⁽ⁿ⁾)|| ч.т.д. Из оц. (4) след. Крит. Ок-я итер: ||(x^(n-1) - x⁽ⁿ⁾)|| < e(1 - ||В||)/||B||.

20. МЗ решения СЛАУ: описание, условия сходимости, оценка погрешности. Метод релаксации.

Модиф. метод простой итерации. Найденное на n-ом шаге значения неизвестных x₁⁽ⁿ⁾, x₂⁽ⁿ⁾ … сразу же вкл. в расчет последующих неизвестных. x⁽ⁿ⁺¹⁾ = B₁x⁽ⁿ⁺¹⁾ + B₂x⁽ⁿ⁾ + c. В₁ – нижняя D матрица, на главной диаг – 0. В₂ – верхняя D матрица, на главной диаг – 0. В = В₁ + В₂. Коэфф. по темже ф-лам, что и в МПИ: b_ij = - a_ij/a_ii; c_i = b_i/a_ii. Расчетная ф-ла: x_i⁽ⁿ⁺¹⁾ = S_i=1^i-1b_ijx_j⁽ⁿ⁺¹⁾ + S_j=i+1^mb_ijx_j⁽ⁿ⁾ + c₁, i = 1, …, m.

Метод релаксации – дальнейшая модификация метода Якоби. В нем, как и в Зейделе, находимые Х используются на этом же шаге, но формула выглядит так: . ω=0..2– коэффициент релаксации.

21. Каноническая форма записи расчетных формул итерационных методов. МПИ с оптимальным выбором параметра.

Ax=b. (x⁽ⁿ⁺¹⁾–x⁽ⁿ⁾)/+Ax⁽ⁿ⁾=b. Расчетная ф-ла МПИ с оптим. выбором параметра: x⁽ⁿ⁺¹⁾=x⁽ⁿ⁾-(Ax⁽ⁿ⁾–b). x⁽ⁿ⁺¹⁾=(E–A)(= B)x⁽ⁿ⁾+b. ( x⁽ⁿ⁺¹⁾ = Bx⁽ⁿ⁾ + c ). Для того, чтобы метод сход., надо ||B|| < 1, т. е. ||E - A|| < 1  условие сходимости.  = 2/(min + max).  - собственные числа матр. А. Условие сходимости будет выполнено и при   (0, 2/max).

МПИ с оптимальным выбором итерац. параметра. Расчетная ф-ла: х(n+1) = x⁽ⁿ⁾ – (2/m+M)f(x⁽ⁿ⁾). m и M – min и max f '(x), x  [a, b].