Абсолютная и относительная погрешности вектора (7 видео)

Абсолютная и относительная погрешности вектора

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

Нормой вектора называется число , удовлетворяющее трем аксиомам:

1) причем = 0 тогда и только тогда, когда = 0;

2) для любого вектора и любого числа ;

3) для любых векторов и .

Наиболее употребительными являются следующие три нормы:

, , .

Абсолютная и относительная погрешности вектора вводятся с помощью формул:

и .

Нормой матрицы называется величина . Введенная норма обладает свойствами, аналогичными свойствам нормы вектора:

1) причем = 0 тогда и только тогда, когда A = 0;

2) для любой матрицы A и любого числа ;

3) для любых матриц A и B;

4) .

Каждой из векторных норм соответствует своя подчиненная норма матрицы:

, , .

В оценках вместо нормы используется евклидова норма матрицы

, так как .

Абсолютная и относительная погрешности матрицы вводятся аналогично погрешностям вектора с помощью формул:

, .

ПРИМЕР 1. Вычисление норм вектора и матрицы.

ПРИМЕР 2. Вычисление норм матрицы.

Пусть рассматривается система линейных алгебраических уравнений

В матричной форме записи она имеет вид . Будем предполагать, что матрица системы задана и является невырожденной. Известно, что в этом случае решение системы существует, единственно и устойчиво по входным данным.

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

Теорема об оценке погрешности решения по погрешностям входных данных.

Пусть решение системы , а x* — решение системы A*x*=b*, тогда , где — относительное число обусловленности системы.

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

ПРИМЕР 3. Оценка числа обусловленности и эксперимент.

Метод Гаусса. Рассмотрим метод Гаусса (схему единственного деления) решения системы уравнений. Прямой ход состоит из m-1 шагов исключения.

1 Шаг. Исключим неизвестное из уравнений с номерами i = 2,3. m. Предположим, что . Будем называть его ведущим элементом 1-го шага.

Найдем величины , i=2,3,. m , называемые множителями 1-го шага. Вычтем последовательно из второго, третьего, . m vго уравнений системы первое уравнение, умноженное соответственно на . В результате 1-го шага получим эквивалентную систему уравнений:

Аналогично проводятся остальные шаги. Опишем очередной k-ый шаг. Предположим, что ведущий элемент . Вычислим множители к-го шага:, i=k+1. m и вычтем последовательно из (k+1)-го, . m v го уравнений системы k-ое уравнение, умноженное соответственно на

.После (m-1)-го шага исключения получим систему уравнений

матрица которой является верхней треугольной. На этом вычисления прямого хода заканчиваются.

Обратный ход. Из последнего уравнения системы находим . Подставляя найденное значение в предпоследнее уравнение, получим . Далее последовательно находим неизвестные .

LU разложение матрицы. Представим матрицу A в виде произведения нижней треугольной матрицы L и верхней треугольной U.

Введем в рассмотрение матрицы

Можно показать, что A = LU. Это и есть разложение матрицы на множители.

ПРИМЕР 4. Разложение матрицы A на множители.

ПРИМЕР 5. Решение системы уравнений с помощью LU — разложения матрицы.

Исправляем ошибки: Нашли опечатку? Выделите ее мышкой и нажмите Ctrl+Enter

Содержание

Норма вектора. Некоторые свойства векторных норм. Абсолютная и относительная погрешности. Сходимость.
Абсолютная и относительная погрешности 1 1
Главная > Документ
🎬 Видео

Видео:урок №12 Абсолютная и относительная погрешности 7 класс алгебраСкачать

Норма вектора. Некоторые свойства векторных норм. Абсолютная и относительная погрешности. Сходимость.

Некоторым обобщением понятия длины вектора (оценкой величины вектора) является величина, называемая норма вектора. Функция

является нормой вектора, если она обладает следующими свойствами [112]:

Чтобы отличить одну норму от другой, используются индексы при двойной черте.

Полезный класс векторных норм — это п-нопмы. определяемые как

Наиболее важными из /?-норм являются 1. 2 и 00 ноомы:

— норма по модулю (частный случай (2.1.36) при р — 1);

— «евклидова» норма (частный случай (2.1.36) при р = 2);

— максимум модуля для элементов вектора (частный случай (2.1.36) при р—> со).

Очевидно, что евклидова норма ||3с|| = у](х,х) . Это соответствует естественному понятию длины вектора в двумерном и трехмерном пространстве. Единичным вектором по отношению к норме || • || называется вектор

х, удовлетворяющий равенству ||3с|| = 1.

Классический результат о «-нормах — неравенство Гелъдеоа

Очень важным частным случаем этого неравенства является неравенство Коши-Шварца:.

Все нормы в R» эквивалентны, т.е. для двух норм || • ||_а и || • ||_/; в R»

существуют положительные константы с, и с,, такие, что

для всех х из пространства R«. Например, для вектора х из R» имеем:

В вычислительной математике большую роль играет понятие «близости» двух векторов. Это соответствует понятию «расстояния», определяемому формулой

т.е. расстояние между векторами равно норме от их разности:

Оценка близости двух векторов используется для определения погрешности решения в итерационных методах.

Пусть вектор Т пространства R» есть аппроксимация к вектору х пространства R«. Для заданной векторной нормы || • || будем говорить, что

есть абсолютная погрешность Т, а при хфО формула

задает относительную погрешность х’.

Сходимость. Будем говорить, что последовательность векторов х‘, х 2 , х к , . сходится к вектору х, если

Отметим, что вследствие приведенных выше свойств векторных норм сходимость в а-норме влечет сходимость в Д-норме и наоборот.

Видео:Погрешность - это просто. Абсолютная и относительная погрешность. ВПР. ОГЭ. ЕГЭСкачать

Абсолютная и относительная погрешности 1 1

Главная > Документ

Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

По свойству нормы (3.2)

|| A|| l = | A ( x ) k |  || A ( x )|| l  || A|| l  || x || l .

Так как || x || l = 1 , выполняется равенство || A ( x )|| l = || A || l  || x || l , т. е. l — норма минимальна.

Пусть при суммировании по столбцам максимальная сумма абсолютных величин элементов матрицы достигается в столбце с номером k

|| A || m =.

Координатный столбец образа базисного вектора e k равен k — му столбцу матрицы A , а

|| A ( e k )|| m = || A || m .

Так как || e k || m = 1 , m — норма минимальна.

Сферическая норма оператора не является минимальной. В евклидовом пространстве для любого вектора x

= ( A ( x ), A ( x )) = ( x , A T A ( x ))  0 .

Оператор B = A T A – самосопряженный и неотрицательный. Пусть Sp ( B ) = , s  n,  1 >… >  r  0. Собственные векторы оператора B , отвечающие различным собственным значениям, ортогональны. Любой вектор x  V является линейной комбинацией собственных векторов

x = x 1 + … + x r , B ( x j ) =  j x j , j =1, …, r .

= ( x , B ( x )) =  1 ( x 1 , x 1 ) + … +  r ( x r , x r )   1 (( x 1 , x 1 ) + … +( x r , x r )) =  1 ( x , x ).

Для ненулевого собственного вектора x 1 выполняется строгое равенство

=  1 (( x 1 , x 1 ).

Следовательно, минимальной нормой оператора в евклидовом пространстве является норма

|| A || s = ,

называемая спектральной. Здесь  1 – наибольшее собственное значение матрицы B = A T A . Характеристический многочлен матрицы B представим двумя выражениями

det ( B —  E ) = ( —  ) n +  1 ( —  ) n-1 + … +  n =

где d j – кратность собственного значения  j . Коэффициент  1 называется следом матрицы B

 1 = tr ( B ) = .

След матрицы выражается через собственные значения

 1   1 = d 1  1 + … + d r  r  ( d 1 + … + d r )  1 = n  1 .

(3.3) .

3.2 Пример. Найти сферическую и спектральную нормы матрицы

A = .

Решение: || A || n = = 9.

B = A T A = .

det ( B —  E ) = = =

= ( 36 —  )(  2 — 29  +132 ).

Наибольшее собственное значение равно 36 (сумма двух других равна 29 ). Итак, || A || s = 6.

Если матрица A – симметрическая, то собственные значения B равны квадратам собственных значений матрицы A и спектральная норма || A || s равна наибольшему по абсолютной величине собственному значению матрицы A .

3.3 Пример. Найти сферическую и спектральную нормы матрицы

A = .

Решение: Вычислим характеристический многочлен матрицы A

det ( A —  E ) = =

= .

Итак, Sp ( A ) = . Следовательно, || A || s = 7 . Квадрат сферической нормы матрицы равен сумме квадратов ее собственных значений с учетом их кратности

|| A || n =  10,1.

Для норм операторов выполняются следующие свойства:

3.6 Предложение. У самосопряженного оператора l — и m -нормы совпадают.

Самосопряженный оператор имеет симметрическую матрицу.

3.7 Предложение. Любой элемент матрицы по абсолютной величине не превосходит любой ее нормы

a ij  ||A||, i, j = 1, …, n.

Доказательство. Для l -, m -, n — норм утверждение очевидно из определения. Проверим утверждение для спектральной нормы. Согласно определению нормы оператора в евклидовом пространстве для базисного вектора e j имеем

|| A ( e j )|| n  || A || s || e j || n .

Норма || e j || n = 1, а координатный столбец вектора A ( e j ) равен j — му столбцу матрицы A . Итак,

|| A ( e j )|| n =  || A || s , j = 1, …, n ,

откуда следует доказываемое утверждение.

3.8 Предложение. Норма произведения операторов не превосходит произведения их норм

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

|| AB || = 

Для n — нормы доказательство следует из неравенства Буняковского

Теория погрешностей в нормированном пространстве. Пусть в линейном нормированном пространстве V задан оператор A : V  V . Перенесем основные понятия теории погрешностей на векторы и операторы.

3.9 Определение. Приближением вектора ( оператора ) называется вектор x ( оператор A ), близкий к точному x * ( A * ) и заменяющий его в вычислениях.

r x = x – x* ( R A = A – A* )

называется погрешностью вектора ( оператора ).

Предельной абсолютной погрешностью вектора ( оператора ) называется любое положительное число  x ( A ) , удовлетворяющее условию

|| r x ||   x ( ||R A ||   A ).

Предельной относительной погрешностью вектора ( оператора ) называется любое положительное число  x (  A ) , удовлетворяющее условию

|| r x || / || x *||   x ( || R A || / || A *||   A ).

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

|| x *|| = || x – ( x – x * )||  || x || + || r x ||  || x || +  x ,

|| x || = || x * + ( x – x * )||  || x *|| + || r x ||  || x *|| +  x ,

откуда получаем интервальную оценку

|| x || –  x  || x *||  || x || +  x .

Аналогично выводится оценка для оператора

|| A|| –  A  || A*||  || A|| +  A .

Следовательно, для вектора и оператора остаются справедливыми формулы (1.2), (1.3) и при малых погрешностях (1.4), при замене абсолютных величин на нормы.

3.4 Пример. В пространстве с n — нормой вычислен вектор

x = ( 2,97654; 0,01275; -4,00152 )

с предельной относительной погрешностью  x = 10 -4 . Записать координаты вектора с сохранением одной сомнительной цифры.

Решение: || x || n = = 4,987  5 . По формуле (1.4)

 x = || x || n  x = 5  10 -4 . Погрешность координат вектора оценим согласно (3.2)

| x j – x j *|  || r x || n   x = 5  10 -4 .

x = ( 2,9765  5  10 -4 ; 0,0128  5  10 -4 ; -4,0015  5  10 -4 ).

3.5 Пример. Координаты вектора x вычислены с 4 верными знаками

x = ( 2,97654; 0,01275; -4,00152 ).

Найти предельную относительную погрешность вектора  x в l -, m -, n — нормах.

Решение: Предельные абсолютные погрешности каждой из трех координат вектора x равны соответственно 10 -3 , 10 -5 , 10 -3 . Погрешность  x находим по формуле (1.4):

в l — норме || x || l = 4,00152  4, || r x || l  10 –3 ,  x = ( 1 / 4 ) 10 –3 ;

в m — норме || x || m = 2,97654 + 0,01275 + 4,00152 = 6,9908  7,

|| r x || m  10 –3 + 10 –5 + 10 –3  2 10 –3 ,  x = ( 2 / 7 ) 10 –3 ;

в n- норме || x || n  5, || r x || n  10 –3 ,  x = ( / 5 ) 10 -3 .

3.6 Пример. Все элементы квадратной матрицы A вычислены с предельной абсолютной погрешностью . Найти предельную относительную погрешность  A матрицы.

Решение: Найдем предельную абсолютную погрешность  A матрицы. Из определения нормы вытекает, что в l -, m -, n — нормах  A = n . Следовательно,

где в каждом случае используется соответствующая норма. Для спектральной нормы воспользуемся неравенством || R A || s  || R A || n . Тогда формула останется справедливой и для спектральной нормы.

3.7 Пример. Все элементы квадратной матрицы A вычислены с предельной относительной погрешностью  . Найти предельную относительную погрешность  A матрицы.

Решение: По условию все элементы матрицы R A удовлетворяют условию | r ij |  | a ij |  . Тогда в l -, m -, n — нормах || R A ||  || A ||  и

Рассмотренная задача имеет прикладное значение. При переводе в двоичную систему счисления каждое число представляется t — разрядной двоичной дробью. Относительная погрешность представления числа  = q –( t -1) /  1 . В двоичной системе q =2,  1 = 1. Отсюда вытекает, что предельная относительная погрешность матрицы при переводе в двоичную систему равна  A = 2 –( t -1) .

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

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

( A + R A )( x + r x ) = b + r b .

Разрешая уравнение для погрешности

A ( r x ) = r b — R A ( x + r x )

r x = A -1 ( r b ) — A -1 R A ( x + r x )

и после перехода к нормам

|| r x ||  || A -1 |||| r b || + || A -1 |||| R A || (|| x || + || r x ||).

Разделим правую и левую части неравенства на || x ||

|| r x || / || x ||  || A -1 |||| r b || / || x || + || A -1 |||| R A || ( 1 + || r x || / || x ||).

Из точного уравнения после перехода к нормам получим || b ||  || A ||  || x ||. Заменим в правой части || r b || / || b ||, || r x || / || x ||, || R A || / || A || на предельные относительные погрешности соответственно  b ,  x ,  A . Тогда правая часть неравенства будет представлять предельную относительную погрешность решения

|| r x || / || x ||  || A -1 |||| A ||  b + || A -1 |||| A ||  A ( 1 +  x ) =  x .

Величина ( A ) = || A -1 |||| A || зависит от определения нормы и называется мерой обусловленности матрицы. Предельная относительная погрешность решения определяется формулой

(3.4)  x = .

Особый интерес представляет спектральная мера обусловленности. Спектральная норма || A || s = определяется по наибольшему значению спектра матрицы B = A T A ,

Sp ( B ) = ,  1 > …>  r .

Спектр матрицы ( A -1 ) T A -1 = ( AA T ) -1 определяет || A -1 || s . Матрицы A T A и AA T имеют одинаковый спектр, а Sp (( AA T ) -1 ) = . Итак, в спектральной норме мера обусловленности матрицы  s ( A ) = равна квадратному корню из отношения наибольшего и наименьшего собственных значений матрицы B = A T A . Для симметрической матрицы A мера обусловленности равна отношению наибольшего и наименьшего по абсолютным величинам собственных значений матрицы A . Из определения следует, что для любой матрицы  s ( A )  1.

3.8 Пример. Найти меру обусловленности матрицы

A = .

Решение: В примере 3.3 получен спектр симметрической матрицы A Sp ( A ) = . Значит,  s ( A ) = 3,5.

3.9 Пример. Найти меру обусловленности матрицы

A = .

Решение: В примере 3.2 вычислен характеристический многочлен матрицы B = A T A

det ( B —  E ) = ( 36 —  )(  2 — 29  +132 ).

Наибольшее и наименьшее собственные значения равны  1 = 36,  r = 264 / ( 29 + ).

 s ( A ) =  2,52.

3.10 Пример. Оценить погрешность решения системы уравнений

при изменении правой части

и сравнить с реальной погрешностью.

Решение: Исходная система имеет решение x = ( 1, 0 ), измененная система – решение x = ( 0,9; 0,1 ). Погрешность решения r x = ( -0,1;0,1 ). В n — норме относительная погрешность || r x || / || x || = .

Вычислим меру обусловленности матрицы. Характеристический многочлен матрицы

A T A =

f (  ) =  2 – ( 10 –2  10 –3 +10 -6 )  + 10 –6

имеет корни  1  10 и  2  10 –7 . Значит,  s ( A ) = 10 4 .

Погрешность правой части r b = ( -0; 10 -4 ). В n — норме  b = . По формуле (3.4), полагая  A = 0, получим предельную относительную погрешность решения  x = , превышающую реальную в раз.

Вычисление спектральной нормы и меры обусловленности матрицы. У положительно определенной матрицы B = A T A имеем

Sp ( B ) = ,  1 >… >  r  0, r  n.

Воспользуемся разложением произвольного вектора x в сумму взаимно ортогональных собственных векторов матрицы B

x = x 1 + … + x r , B ( x j ) =  j x j , j = 1, …, r .

( B i ( x ), B i ( x )) = .

Зададим вектор y (0) произвольно и построим вычислительный процесс

z (i) = A ( y (i) ), y (i+1) = A T ( z (i) ) / | y (i) |.

Докажем, что y ( i ) = B i ( y (0) ) / | B i -1 ( y (0) )|. При i = 1 равенство верно. Индукция по i . Допустим, что равенство верно при i , и докажем, что оно верно при i +1.

y (i+1) = A T ( A ( y (i) )) / | y (i) | = B ( B i ( y (0) ) / | B i-1 ( y (0) )|) / | y (i) | = B i+1 ( y (0) ) / | B i ( y (0) )|.

У матрицы B  = E – ( 1 /  1 ) B наибольшее значение спектра

 max = 1 –  r /  1 = 1 – .

Для вычисления  max изменим вычислительный процесс следующим образом:

z (i) = A ( y (i) ), y (i+1) = ( y (i) – ( 1 /  1 ) A T ( z (i) )) / | y (i) |

при произвольном задании y (0) . В итоге двукратного умножения матрицы на вектор получим

y ( i +1) = ( E – ( 1 /  1 ) B )( y ( i ) / | y ( i ) |) = B  ( y ( i ) / | y ( i ) |).

Следовательно,  max . Спектральная норма матрицы вычисляется по формуле

(3.5)  s ( A ) = .

§ 4 Системы линейных уравнений

Разложение квадратной матрицы в приизведение треугольных. Пусть дана система уравнений A ( x ) = b .

4.1 Теорема. Какова бы ни была квадратная матрица A с отличными от нуля угловыми минорами

a 11  0,

ее всегда можно разложить в произведение

где S и T соответственно левая и правая треугольные матрицы.

Доказательство. По условию теоремы s ik = 0 при k > i и t kj = 0 при k j . Тогда

a ij =.

Отсюда s 11 t 11 = a 11 , s ji = a j1 / t 11 , t 1j = a 1j / s 11 , j = 2, …, n;

s ii t ii = , s ji = () / t ii , t ij = () / s ii , j = i+1, …, n.

Итак, решение существует, если s ii  0 и t ii  0.

Допустим, что при некотором p получим s pp t pp = 0. В этом случае возможно разложение A p = S p T p , где A p , S p , T p – матрицы угловых миноров p — го порядка. Тогда

det ( A p ) = det ( S p ) det ( T p ) = = 0,

что противоречит условию теоремы.

Если фиксировать n диагональных элементов ( t ii = 1, i = 1, …, n ), то полученное решение будет единственным.

Метод Гаусса . Представим матрицу A произведением треугольных матриц и сведем задачу к решению двух систем

S ( y ) = b и T ( x ) = y .

Фиксируем диагональные элементы матрицы T , положив t ii = 1, i = 1, …, n . Столбец свободных членов b присоединим к матрице A , присвоив ему номер n +1 ( a i n +1 = b i ). Столбец y получим на месте ( n +1 )-го столбца матрицы T .

Решение системы S ( y ) = b составляет прямой ход метода Гаусса.

s i1 = a i1 , i = 1, …, n, t 1j = a 1j / a 11 , j = 2, …, n+1;

s ji = , j = i, …, n, t ij = () / s ii , j = i+1, …, n+1.

Обратный ход метода Гаусса состоит в решении системы T ( x ) = y . Координаты вектора y составляют ( n +1 )-й столбец матрицы T ( y i = t i n +1 ).

x n = y n / t nn , x i = y i – , i = n-1, …, 1.

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

4.1 Пример. Решить методом Гаусса систему линейных уравнений

при вычислении с тремя значащими цифрами.

Решение: Запишем расширенную матрицу системы. При прямом ходе метода Гаусса первую строку расширенной матрицы разделим на 10 -4 и вычтем из второй. Во второй строке появятся четырехзначные числа, которые необходимо округлить до трех знаков. На этом прямой ход закончен, матрица A приведена к треугольному виду.

обратный ход

Выполнив обратный ход, получим x 1 = 0, x 2 = 1. Решение системы с тремя верными знаками после запятой x 1 = 1, x 2 = 1. Итак, вычислительная погрешность существенно исказила результат. Потеря точности произошла при вычитании чисел с сильно различающимися порядками.

Метод Гаусса с выбором главного элемента позволяет исключить вычитание больших чисел. Главным называется наибольший по абсолютной величине коэффициент при неизвестных в ведущей строке расширенной матрицы. После деления на главный элемент коэффициенты при неизвестных в ведущей строке по абсолютной величине не больше единицы. При прямом ходе метода Гаусса ведущая строка умножается на элемент ниже расположенной строки и вычитается из нее. При этом в преобразуемой строке из каждого коэффициента вычитается число, не превышающее один из элементов этой строки. Порядок элементов существенно не изменяется. Однако, если вычитание ведущей строки ведет к уменьшению порядка всех коэффициентов при неизвестных, происходит потеря точности, связанная с вычитанием близких чисел. Поэтому процедура выбора главного элемента, усложняя метод, не гарантирует полностью от проблем с вычислительной погрешностью.

Метод квадратного корня . У положительно определенной матрицы A все угловые миноры положительны и являются доминирующими. Отпадает необходимость в поиске главного элемента. Симметрическая матрица A разлагается в произведение треугольных матриц A = ST , таких, что S = T T . Достаточно вычислять одну матрицу T . Метод Гаусса, адаптированный к линейным системам с положительно определенной матрицей, называется методом квадратного корня . Его реализация имеет вид ( s ij = t ji , a i n+1 = b i , t in+1 = y i )

t 11 = , t 1j =a ij / t 11 , j = 2, …, n+1;