билеты по матмоду

1.Опр-я абс. и отн. погр-й. Оц.абс. и отн. погр-ти. Погр-ть арифм. оп-й. Понятие вер. цифры.

Абс. Погр-ть - , где а – точное зн-е ф-и, а* - прибл. Граница абсолютной погрешности - Относительная погрешность - . Граница -

Оценки погрешностей: ),

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

Для верхней абсолютной погрешности арифметических суммы и разности полагают, что ; для относительной (если a, b- ненулевые числа одного знака) –

Если и , то

Знач. цифры – все цифры числа, нач. с 1 ненулевой слева. Зн-я ц. наз-ся верной, если абс. Погр-ть этого числа не превосходит ед. разр., соотв. цифре. Если у приближ. числа не указана погр-ть, то все его знач. цифры –в.ц.

2. Оценка погр-ти ф-ии многих пер-х по погр-м арг-в.

Y=f(x)=f(x1,…,xn); y*=f(x*)=f(x1*,…,xn*).

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

Предст. Чисел в эвм. x=αn,…,α0,β1,…,βm, α,β<0

Маш. ∞ - самое большое число, предст. в эвм.

Маш. 0 – мин. Положит. Число, предст. в ЭВМ.

Маш. ε – вел. Отн. Погр-ти, в предст-ии числа в эвм.

Особ-ти маш. Арифм.: x=αn*αn-1*…*β1*…*βm. Правила маш. Арифм: a+b=a*+b*; δ(a)=Δa/|a|; Δa=|a|*δ(a)

Пример:10.5+0.125. 10,5=8+2+1/2=1*2^3+0*2^2+1*2^1+0*2^0+1*2^(-1); 0.125=0*2^(-1)+0*2^(-2)+1*2^(-3); 10.5=1010.1, 0.125=0.001; 1010.1=0.10101*2^4, 0.001=0.0000001*2^4; дальше сложить в столбик.

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

Обусл. Вычисл. Зад – чувств-ть реш-я зад к малым погр-м вх.д.

Задача наз-ся хорошо обусл., если малым погр-м вх.д. отв. Малые погр-ти реш-я, и плохо обусл., если происходят сильные изменения реш-я.

Число обусл-ти. – коэфф. Возм. Возр-я погр-ти в реш-ии по отн. к порг-м вх.д. Абсолютное число обусл.: _: (у*)  _*(х*). Относит. число обусл.: _: (у*)  _*(х*). Задача хор. обусл, если _  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*]}f`(x)*x*/f*.

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

Пост. Зад.: найти Этапы решения:

1. Локал-я корней – выд. Отр-в, в кот-ых сод. Корень ур-я. Способы – табличный и графический.

2. уточнение корня – выч-е корня с зад. точн..

В отр. Лок-ции [a,b]сод только 1 корень.

Прямой метод – за конечное число шагов позв. Найти точное реш-е при усл-ии отс-я погр-ти.

Итерационные методы – м., получ. ∞ посл-ть прибл-й к реш-ю. итер. Метод сходится, если lim (xn)=x, корень

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

Опис-е м.: пусть [a,b] – отр.лок-ции корня х, f(x) непрер. на [a,b], f(a)*f(b)<0

1.обозн. [a0,b0]=[a,b], x0=(a0+b0)/2, если f(a)*f(b)<0, то новый отр лок-ции – [a1,b1]=[a0,x0] и наоборот

2. (к+1) шаг м.:xk=(ak+bk)/2 – сер. [ak,bk]:1)f(xk); 2)если f(xk)*f(ak)<0, то [ak+1,bk+1]=[ak,xk] и наоборот;3)xk+1=(ak+1+bk+1)/23.для прибл. хк справ. Нер-во (b-a)/2ⁿ⁺¹

Критерий окончания: = х* ± . х*  [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₂((b0 – a0)/ε); Скорость сход.: 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⁽ⁿ⁾ - | qⁿ|x⁽⁰⁾ - |, |x⁽ⁿ⁾ - | (q/(1 – q))|x^(n-1) – x⁽ⁿ⁾|. Д-во. = ( ). x⁽ⁿ⁾ = (x^(n-1)). x⁽ⁿ⁾ - = (x^(n-1)) - ( ) = '(ξ)(x^{(n – 1)} - ), ξ[x^(n-1), x].|x⁽ⁿ⁾ - | q|x^(n-1) - | …  qⁿ|x⁽⁰⁾ - |. |x(n) – x|= (x^(n-1)) - ( ) = (x^(n-1)) – x⁽ⁿ⁺¹⁾ + x⁽ⁿ⁺¹⁾ - ( ) = (x^(n-1)) – (x⁽ⁿ⁺¹⁾)+ (x⁽ⁿ⁺¹⁾) - ( ) = '(ξ)(x^(n-1) – x⁽ⁿ⁾) + (ξ₂)(x⁽ⁿ⁾ - ). Крит.ок-я: q/(1-q)*|xn-xn-1|≤ε -> |xn-xn-1|≤ε*(1-q)/q

8. МПИ с пар-м. Прив-е ур-я к виду

Привед. ур-я к виду, уд. Для. Итер-й: f(x)=0 <-> x=x-αf(x), α – параметр. φ(x)=x-αf(x), φ`(x)=1-αf`(x), |φ`(x)|=|1-αf`(x)|<1, 0< αf`(x)<2, f`(x)на отрезке лок-ции должна быть знакопост. Знак α должен совп. со зн. Произв. f`(x) на [a,b] Оптимальное зн-е пар-ра α: f`(x)>0; M1=max(f`(x)), m1=min(f`(x)); q(α)=|1-αf`(x)|; МПИ с выбором пар-ра: f(x)=0; M1=max(f`(x)), m1=min(f`(x)); xn+1=xn-αf(xn); ; крит.ок-я: |xn+1-xn|=(1-q)ε/q

9. Метод Ньютона реш-я нелин. Ур-я: опис. м, теорема о сходимости, критерий окончания.

x^{(n + 1)} = x⁽ⁿ⁾ – f(x⁽ⁿ⁾)/f '(x⁽ⁿ⁾) – расч. Ф-ла.

М.н. обл. более выс.ск-ю сх-ти. Если – простой, т.е. f`( , а в нер-й окр-ти сущ-т f’’(x), то сущ. Окр-ть , где имеет место априорная оц.:| , кот-ая обозн-т квадр-ю ск-ть сх-ти мН. Апостериорная оценка:

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

10. Упрощ. м. Ньютона, м.сек-х, м. ложного положения. Алгоритмы и порядок сходимости методов. Геометрическая интерпретация.

Упрощ. м.Н.: xk+1=xk-f(xk)/f`(x0), k=0,1,.. отличие от мН – производная счит. Только 1 раз. Сх-ть линейная.

М. сек-х: xn+1=xn-(f(xn)(xn-1-xn))/(f(xn-1)-f(xn)), x0,x1 – старт-е точки лок-ции. Пусть – простой кор.ур-я, f(x) дважды дифф-ма и f``( )=0. Тогда при произв. Выборе нач прибл. х0 и х1 из σ-окр-ти корня м.сек-х сх-ся со скор-ю р=(1+v5)/2=1,68. . труд-ть м.сек-х<мН

М.ложн.пол-я: f`(xn)=(f(z)-f(xn))/(z-xn); xn+1=xn-(f(xn)(z-xn))/(f(z)-f(xn)), z – т.ложного пол-я. Сх.лин.

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

В реальн. вычисл. $ такая d-окр-ть корня в которой знак вычисл. ф-ии f*(x) не совп. со знаком f( )из-за погр-ти вычисл. Становится невозм. опред. знач. корня. Этот отр-к ( -d, +d) наз. Инт-л неопр-ти. Если [ -d, +d], то f(x)»f( )+f'( )(x- ) ®D ³ f(x) » f '( )(x - ).

|x - |£ D /|f '( )|, |x - |¬ погр-ть рез-та. Dу £ nDDx, nD - число обусл-ти. Dх £ nDD (f*), n_D = 1/|f '(x)|. Из этой оценки вытекает, что зад. выч-я кр. корня явл. зад. вычисл. плохо обусл-го зн-я. Если корень простой, т.е. f`(x)≠0, то зад. Хор. Обусл.

12. Нормы векторов. Подчиненная норма матрицы. Наиболее употребительные нормы.

В пространстве 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||.

13. Обусл-ть зад. р-я СЛАУ. Число обусл-ти. Оц. погр-ти рез-та по погр-м вх. д.

Ax=b, реш.возм.сист. Ax*=b*, A*x*=b или A*x*=b*. для 1 и 2 типа δ(x*) связана с δ(b*) и δ(A*): δ(x*) ≤cond(A) δ(b*); δ(x*) ≤cond(A) δ(A*), а для 3 типа, при cond(A) δ(A*)<<1, нер-м δ(x*) ≤cond(A)(δ(A*)+ δ(b*)), где cond(A)=||A||*||A^-1|| — число обусл-ти. его пор. приблизит. пока-т max возм. потерю в.ц. при реш. возм-й СЛАУ. Сист. с большим числом обусл-ти м-цы, cond(A)>>1, считают плохо обусл-ми.Св-ва: 1)cond(E)=1; 2) Cond(A)≥1; 3) cond(αA)=cond(A), Ɐα≠0

14. М.Гаусса(сх. ед. дел.): опис-е м., труд-ть м.