18529

Меры погрешности решения

Доклад

Информатика, кибернетика и программирование

Меры погрешности решения Пусть x вычисленное решение СЛАУ Ax=b. Существуют две общеупотребительные меры погрешности в х: вектор ошибки е = х х 1 и невязка r = b Ax = Ax x = Ae

Русский

2013-07-08

359 KB

2 чел.

Меры погрешности решения

Пусть x* - вычисленное решение СЛАУ Ax=b.

Существуют две общеупотребительные меры погрешности в х*:

вектор ошибки

е = х - х*                                                                (1)

и невязка

r = b - Ax* = A(x - x*) = Ae                                              (2)

Невязка – это количественная мера несоответствия между правыми и левыми частями уравнений системы при подстановке в них вычисленного решения. Теория матриц говорит, что при невырожденной матрице А из равенства нулю ошибки следует равенство нулю невязки и наоборот. Но эти два вектора не обязаны быть «малы» одновременно.

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

Квадратная матрица A называется вырожденной, если ее определитель равен нулю: det(A)=0. 

Если матрица А почти вырождена (т. е. если малым изменением уравнений систему можно сделать вырожденной), то, даже при игнорировании ошибок  округления, ничтожные возмущения коэффициентов системы могут приводить к большим изменениям решения. Поэтому для таких систем уравнений нереалистично рассчитывать на то, что х* будет хорошим приближенным решением. Если известно, что матрица далека от вырожденности, то и невязка, и ошибка будут достаточно малы.

Обусловленность матрицы

 

 Обусловленность – это внутреннее свойство матрицы, не связанное с тем, как именно решается система уравнений. Число обусловленности определяется отношением:

,                                                           (3)

где и - максимальное и минимальное собственные значения.

Проиллюстрируем физический смысл собственных значений на следующем примере.

Пример. Рассмотрим резистивную схему рис. 1а

    Y1                                            Y1`

  E                                       E                                              E                        Y1``                                                                                    

     1   Y2                                     1                                                             2

                                                                 Y2`                                               Y2``

     2  

   Y3

a                                              б                                                 в    

Рис. 1. Резистивные схемы: a) исходная; б) преобразованная для первого узла;

          в) преобразованная для второго узла.

Получим ММС схемы МУПом:

Преобразуем указанную схему к виду рис. 1б., объединив Y2 и Y3, так что , тогда ММС примет вид                                                                                  

| |*| φ1 | = .

Преобразуем схему  к виду рис. 1в, аналогично объединив Y1 и Y2. ММС примет вид

| |*|φ2| = .

Объединив эти уравнения, получим ММС схемы рис. 1а в виде

                                  (4)

Здесь ненулевые элементы матрицы расположены только по главной диагонали.

Известно, что в этом случае элементы и  являются собственными значениями исходной матрицы .

Легко видеть, что решение системы (4) тривиально, но нетривиальна задача нахождения собственных значений.

Собственные значения для линейных резистивных схем – это собственные проводимости. При анализе переходных процессов собственные значения – это собственные постоянные времени. При частотном анализе – это собственные частоты.

Число cond(A) измеряет, насколько близка к вырожденной матрица А, и насколько чувствительно решение системы  Ax=b к изменениям в А и b. Коэффициенты матрицы и правой части системы линейных уравнений редко бывают известны точно.  Некоторые системы возникают из эксперимента, и тогда коэффициенты подвержены ошибкам  наблюдения.   Коэффициенты  других  систем  записываются формулами, что влечет ошибки округлений при их вычислении. Даже если систему можно точно записать в память машины,  в ходе ее решения почти неизбежно будут сделаны ошибки округлений. Можно показать, что ошибки округлений в гауссовом исключении имеют то же влияние на ответ,   что и ошибки в исходных коэффициентах.

Чтобы уяснить себе смысл числа обусловленности, уточним представление о «почти вырожденности». Если А - вырожденная матрица, то для некоторых b решение х не существует, тогда как для других b оно будет неединственным. Если матрица А почти вырождена, то можно ожидать, что малые изменения в А и b вызовут очень большие изменения в х. С другой стороны, если А - единичная матрица, то b и х - один и тот же вектор. Следовательно, если матрица А близка к единичной, то малые изменения в А и b должны повлечь за собой соответственно малые изменения в х.

Чтобы получить более точную и надежную меру близости к вырожденности,  потребуется ввести понятие нормы вектора. Норма — это число, которое измеряет общий уровень элементов вектора. Наиболее употребительной векторной нормой является евклидова длина:

     .

Однако использование этой нормы сделало бы слишком трудоемкими некоторые из вычислений. Вместо нее мы определим норму вектора из п компонент следующим образом:

Эта норма обладает многими из аналитических свойств евклидовой длины, именно:

                                                    ||х|| > 0,  если х ≠ 0

                                                    ||0||=0,

                                                    ||сх|| = |с|*||х|| для всех скаляров с,

                                                    ||х+у||≤||x||+||y||.

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

Максимум и минимум берутся по всем ненулевым векторам. Заметим, что если матрица А вырождена, то т = 0. Отношение М/т является числом обусловленности матрицы А:

Рассмотрим систему уравнений

Ах = b                                                           (5)

 и другую систему, полученную изменением правой части:

А(х + ∆х) = b + ∆b.                                                         (6)

Будем считать b ошибкой в b, а х – соответствующей ошибкой в х, хотя нет необходимости предполагать, что ошибки малы. Поскольку А (∆х) = ∆b, то определения Миm немедленно ведут к неравенствам:

    ||b|| ≤ M||x||

    ||b|| ≥ m||x||

Следовательно, при М ≠ 0

Величина ||b||/||b|| есть относительное изменение правой части, а величина ||х||/||х|| - относительная ошибка, вызванная этим изменением. Использование относительных изменений имеет то преимущество, что они безразмерны, т.е. нечувствительны к общим масштабирующим множителям.

Полученное неравенство показывает, что число обусловленности выполняет роль коэффициента увеличения относительной ошибки. Изменения правой части могут повлечь за собой изменения в решении, большие в cond (A) раз. Оказывается, что то же самое справедливо и в отношении изменений в коэффициентах матрицы.

Некоторые из основных свойств числа обусловленности выводятся просто. Ясно, что М≥m и потому

cond (A) ≥ 1.

Если Р - матрица перестановки, то компоненты вектора Рх отличаются от компонент вектора х лишь порядком. Отсюда следует, что ||Рх||  = ||х|| для всех х и, значит,

cond(P) = l.

В частности, cond(I)=1. Если А умножается на скаляр с, то и М, и т умножаются на модуль этого скаляра, так что

cond(сA)=cond(A).

Если D - диагональная матрица, то

Так, для матрицы

Имеем М = 5 и m = 1, поэтому cond(D) = 5/1 = 5.

Последние два свойства в известной мере объясняют, почему cond (A) является лучшей мерой близости к вырожденности, чем определитель матрицы А. В качестве крайнего примера рассмотрим диагональную матрицу порядка 100 с числом 0.1 на главной диагонали. Тогда det(A) = 10 -100, что обычно считается малым числом. Но cond(A)=1, и компоненты вектора Ах отличаются от соответствующих компонент вектора х лишь множителем 0.1. Для линейных систем уравнений такая матрица А ведет себя скорее как единичная, а не как вырожденная.

Проиллюстрируем понятие числа обусловленности следующим примером.

Пример 1. Пусть

А= ,          b=  ,

тогда        x= ,   =13.8                =1.

Если заменить правую  часть системы на:

b′= ,

то решением будет вектор

x′= .

Пусть b=b-b′  и ∆x=x-x′. Тогда

=0.01,  =1.63.

Очень малое возмущение, внесенное нами в b, совершенно изменило x. Действительно, относительные изменения равны

=0.0007246, =1.63.

Так как cond(A) характеризует максимальное возможное увеличение, то

.

На самом деле выбранные b и b как раз и дают максимум, так что для этого примера

Предположим, что мы хотим решить систему, в которой а1,1 = 0.1, а все остальные элементы в А и b - целые числа, и cond (A) = 105. Предположим далее, что у нас двоичный компьютер с 24 битами для дробной части числа и что мы каким-то образом умеем вычислять точное решение для системы, уже записанной в память машины. Тогда единственная ошибка будет связана с двоичным представлением числа 0.1, и тем не менее можно ожидать, что

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

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

(А + Е)х* = b,

где Е- матрица, элементы которой имеют величину порядка ошибок округления в элементах матрицы А. Тем самым все ошибки округления могут быть слиты воедино и рассматриваться как единственное возмущение, внесенное в матрицу в момент ее записи в память компьютера; само же исключение осуществляется без ошибок. Поскольку запись почти любой матрицы в память сопровождается возмущениями, сравнимыми с Е, то свойство метода Гаусса - это лучшее, что можно сказать о каком-либо алгоритме решения линейных уравнений. В этом смысле гауссово исключение представляет собой идеальный алгоритм решения системы Ах = b.


 

А также другие работы, которые могут Вас заинтересовать

60514. Meet My Friends. Мої друзі та я 128.5 KB
  We shall speak about English and Ukrainian schools once more. As a result you’ll write a project about your favourite school and the best friend at school.
60515. Мій найкращий товариш і я 135.5 KB
  Мета уроку: практична: актуалізувати лексичний та граматичний матеріал за темами; учбова: продовжувати формувати комунікативні вміння в говорінні та письмі...
60520. Історія комп’ютеризації освіти Голованівського району 817.5 KB
  У газеті Аспект була надрукована стаття у якій автор детально описує початок комп’ютеризації освіти Голованівського району. Дядьки чемно відмовляються від вечері і зникають так само несподівано як і з’явились...
60521. Архитектурный план дома 442.5 KB
  Сегодня мы поговорим про проектирование дома коттеджа и т. Рассмотрим какие рекомендации должен соблюдать дизайнер разрабатывая план частного дома а также план капитального ремонта жилых домов план каркасного дома архитектурный план...