Файл: 15-19.docx

Оценка погрешности решения СЛАУ. Различные нормы векторов и матриц. Неустранимая погрешность. Число обусловленности матрицы и его влияние на относительную погрешность решения СЛАУ.

Нормой вектора является противопоставление вектору x какого-либо скаляра ||x||, отвечающего требованиям:

1. ||x||>0 и ||x||=0 только если x=0

2. ||kx||=k||x|| для любого числа k и вектора x

3. ||y+x||||x||+||y|| для любых векторов x и y

Способы вычисления:

1. взятие суммы значений вектора

по модулю:

2. Нормой является корень суммы квадратов модулей значений вектора:

3) Взятие максимального по модулю значения:

Нормой матрицы а является число

Обладающее основными свойствами:

1. ||A||>0 и ||A||=0 только если A=0

2. ||kA||=k||A|| для любого числа k и матрицы A

3. ||A+B||||A||+||B|| для любых матриц A и B

4. ||AB||||A|| ||B||

Выделяют три вида норм матриц и способа их вычисления, каждая из которых соответствует способу вычисления векторной нормы:

1)Вычисление максимальной суммы элементов матрицы по столбцам:

2) Вычисление норма, используя евклидову норму:

3) Вычисление максимальной суммы элементов матрицы по строке

Рассмотрим влияние значений погрешностей в исходных данных.

1) Пусть значения матрицы заданы и значения ее правой части заданы неточно, тогда решение будет с погрешностью.

Пусть дана Ax=y (1)

значения заданы с погрешностью:

A(x+x)=y+y

Ax+Ax=y+y, вычтем (1), получим:

Ax=y

x=A^-1y

||x||||A^-1|| ||y|| (из x=A^-1y)

||A|| ||x||||y||

||x|| ||A-1|| ||A|| ||y||

||x|| ||y||

||x||cond A ||y||

значит мы определили, что значение относительной погрешности зависит от относительной погрешности правой части и от числа обусловленности системы.

CondA=||A|| ||A^-1|| - число обусловленности матрицы, если оно велико, то матрица плохо обусловлена, если мало, то наоборот.

2) рассмотрим случай когда коэффициенты матрицы заданы неточно

(A+A)(x+x)=y

x=(A+A)^-1 y- A^-1y=(( A+A)^-1 - A^-1)y= A^-1A (A+A)^-1 y

||x||  ||A-1|| ||A|| ||A||

||x+x|| ||A||

||x||CondA||A||

||A||

Пусть в системе правый вектор задан плохо обусловленным правым вектором

x1+0.9x2=1.99 | 1.989903

0.99x1+0.98=1.97 | 1.970106

а) x1=x2=1

б) x1=3 x2=1.0203

Во 2ом случае ошибка составила менее 200%, т.е. это вообще не решение, а число обусловленности равно 39600

Если в матрице присутствуют очень большие и очень маленькие значения (большой разброс в значениях), то матрица плохо обусловлена.

a₁₁x+a₁₂y=z1

a₂₁x+a₂₂y=z₂

y=z1 - x a11

a12 a12

y=z2 - x a21

a22 a22

Если линии пересекаются, то система

совместна.

Мы имеем тот случай, когда погрешность в условии перешла в погрешность решения.

Норма матрицы может быть представлена как отношение максимального и минимального собственного значений матрицы. cond(A) =max/min

Для уменьшения числа обусловленности используют алгоритмы масштабирования, в основе которого лежит переход к другой матрице с меньшим числом обусловленности.

Уинкинсон предложил алгоритм маштабирования:

Ax=Y;

D₁Ax = D₁Y; x= D₂ z;

D₁ = - выбирается так, чтобы не было большого разброса коэффициентов

(коэффициенты это 2 или 10 в различной степени)

D₁ AD ₂z = D₁Y;

новая матрица,у которой число обусловленностей должно быть меньше

Построение интерполяционного многочлена Лагранжа.

Основная задача построения многочлена Лагранжа- снизить трудоемкость построения многочлена:

Pn(x)=an xⁿ+…..+a1x+a0

Пусть даны узлы интерполяции:

(x0,y0)……(xn,yn) и Pn(xi)=yi, i=0,n (функция задающая значения)

Лагранж предложил использование другой формы построения многочлена.

Пусть задана (n+1) точка узлов интерполяции и пусть многочлен представлен в виде:

Pn(x)=y₀b₀(x)+…..+y_nb_n(x),

где yo…..yn- таблично заданные узлы интерполяции

b0…..bn- многочлены степени n

y₀b₀(x0)+…..+y_nb_n(x0)=y0

y₀b₀(x1)+…..+y_nb_n(x1)=y1

………………………..

y₀b₀(xn)+…..+y_nb_n(xn)=yn

гдеbj= 1, i=j

0, ij

bj(x)=Cj(x-x0)(x-x1)…….(x-xn)

Cj(xj-x0)(xj-x1)………..(xj-xn)=1

Cj= 1 .

(xj-x0)(xj-x1)………..(xj-xn)

Pn(x)=yi(x-x0)(x-x1)………..(x-xn)для i=0,n

(xi-x0)(xi-x1)………..(xi-xn)

Тогда интерполяционный многочлен Лагранжа будет иметь вид:

Lj(x)=(x-x0)(x-x1)……(x-xn)

P(n)= )=yiLj(x)для i=0,n

Lj(xi)

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

Итерационные методы широко применяются для решения разностных уравнений мате­матической физики, операторам которых соответствуют ленточные матрицыАвысокого порядка. Общее описание метода итераций для системы линейных алгебраических уравнений: Au=f (1)

Для ее решения выбирается некоторое начальное приближение y₀єH и последовательно находится приближённые решения (итерации) уравнения (1). Значение итерации y_k+1 выражается через известные предыдущие итерации y_k, y_k-1 , …. . Если при вычислении y_k+1 используется только одна предыдущая итерация y_k , то итерационный метод называется одношаговым (двухслойным) методом, если же y_k+1 выражается через две итерации y_kи

y_k-1то метод называется двухшаговым (трёхслойным).

Важную роль играет запись итерационных методов в единой (канонической) форме. Любой двухслойный итерационный метод можно записать в следующей канонической форме:

k=0,1,…, для всех y₀єH, где А: Н→Н- оператор исходного уравнения (1), В: Н→Н - линейный оператор ,имеющий обратный В^-1, к - номер итерации , τ₁ ,τ₂,….., τ_к+1 , - итерационные параметры , τ_к+1>0 . Оператор В может, вообще говоря, зависеть от номера к, для простоты изложения мы предполагаем всюду , что В не зависит от к.

Если В=Е – единичный оператор, то метод

k=0,1,…, для всех y₀єH, называют явным: находится по явной формуле=y_k-(Ay_k-f). В общем случае , при В≠Е, метод называют неявным итерационным методом: для определения надо решить уравнение

, k=0,1,……. (4)

Говорят что итерационный метод сходится в H_D, если

, где Обычно задают некоторую погрешность (относительную) ε>0 , с которой надо найти приближенное решениеy_k, и прекращают вычисление , как только выполняется условие

Итерационные методы: метод простой итерации, метод Зейделя, метод верхней релаксации, стационарные итерационные методы. Итерационные методы сходятся не для любой системы уравнений , но систему уравнений можно изменить, таким образом чтоб итер. метод сходился при любом начальном приближении.

Построение интерполяционного многочлена Ньютона

Задан (n+1)узел интерполяции

P_n(x)=c₀+c₁(x-x₀)+c₂(x-x₀)(x-x₁)+…+c_n(x-x₀) ..(x-x_n-1)

=

Система линейных алгебраических уравнений в «явной» форме. Метод простыx итераций.

Уравнение представлено в явной форме, если неизвестные, находящиеся в зависимости расположены в одной из частей уравнения, а в другой располагаются известные величины.

Метод итераций:

F(x)=0 Система имеет решение

Можно задать начальное приближение.

x=Ф(x)

xk+1=Ф(xk) x=x+AF(x);A>0

Δxk+1= xk+1- xkS(x,y)={x,y;|x*y|<S}

|| Δxk+1||<Eps

|Ф(x)- Ф(y)|<q||x-y||

S(Xo,V) 0<q<1

Пусть выполняется условие :

||Xo-Ф(Xo)|<S(1-q)|

x=Ф(x)- корень уравнения

Условие теоретически проверить тяжело

1)Накладывания жёсткого условия на производную

2)Хорошие начальные произведения

Основные пути: x=Ф(x)

Увеличить скорость сходимости (Зейдель)

Метод интерполяции Ньютона-Грегори, основанный на использовании разделённых разностей

x_i+1-x_i=h- расстояние между узлами интерполяции

Вычисления используя конечные разности

y₀=c₀

y₁=c₀+c₁h

y2=c0+c1h+c2h

……………….

y_n=c₀+…+c_n(n-1)h* *h

y_i=y_i+1-y_i

Δ(Δy_i)=Δ(yi₊₁-y_i)=Δy_i+1-Δy_i=(y_i+2-y_i+1)-(y_i+1-y_i)=y_i+2-2y_i+1+y_i

Δ^ey_i=Δ(Δ^e+1)y_i

C₀=y₀

C₁=(y₁-c₀)/h=(y₁-y₀)/h=Δy₀/h

C₂=(1/2h²)(y₂-c₀-2hc₁)=(1/2h²)(y₂-y₀-2h((y₁-y₀)/h))=(1/2h²)(y₂-y₁-y₁+y₀)=

=(1/2h²)(Δy₁-Δy₀)=(1/2h²)Δ(Δy₀)=Δ²y₀/2h²

c_j=Δ^jy₀/(j!)h^j

P_n(x)=c₀+c₁(x-x₀)+c₂(x-x₀)(x-x₁)+…+c_n(x-x₀) ..(x-x_n-1)