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.


 

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

75303. Немарксистские теории происхождения средневековых городов 33 KB
  Немарксистские теории происхождения средневековых городов. Вопрос о причинах и обстоятельствах возникновения средневековых городов представляет большой интерес. При таком подходе невозможно объяснить коренные причины происхождения городов. Романистическая теория Савиньи Тьерри Гизо Ренуар которая строилась главным образом на материале романизированных областей Европы считала средневековые города и их учреждения прямым продолжением поздних античных городов.
75304. Отечественная историография о происхождении средневекового города 42.5 KB
  Отечественная историография о происхождении средневекового города. Впервые проблема происхождения городского строя в Западной Европе была поставлена в отечественной медиевистике в начале XX в.Впервые в России обращение к городской истории произошло именно в историографическом аспекте. Интересуясь прежде всего проблемами аграрного развития Европы эпохи Средневековья и формируя общую концепцию генезиса феодализма Петрушевский не мог пройти мимо такого интересного сюжета европейской истории как возникновение городов.
75305. Характер, формы и основные этапы социальной борьбы в средневековом городе 35.5 KB
  Средневековые города возникали на земле королей а также светских и духовных феодалов. Они начали борьбу за свое освобождение добиваясь превращения сеньориального города в вольный а его жителей в свободных горожан. Позднее города стали бороться за политические привилегии: право на самоуправление и собственную юрисдикцию. Но это было по силам только очень богатым городам французским английским.
75306. Средневековое цеховое ремесло и его характер 39 KB
  Средневековое цеховое ремесло и его характер. Характерной особенностью средневекового ремесла в Европе была его цеховая организация объединение ремесленников определённой профессии в пределах данного города в особые союзы цехи. Цехи появились почти одновременно с возникновением городов. хотя окончательное оформление цехов получение специальных хартий от королей запись цеховых уставов и т.
75307. Производительные силы Западной Европы в V-XV веков 43.5 KB
  Производительные силы средневекового общества это люди с присущими им особенностями сознания трудовыми навыками природная среда их обитания и созданные ими в процессе жизнедеятельности орудия технологии и формы организации труда. Его характеризовали ручные орудия и низкая производительность труда отсутствие скольконибудь значительных материальных ресурсов простое нерасширенное воспроизводство. Даже крупные владения феодалов чаще всего представляли собой конгломерат более или менее значительных усадеб деревень или их групп...
75308. Культура Западной Европы в V-XI веках 43 KB
  Культура Западной Европы в VXI вв. Искусство Западной Европы в средние века. Книга представляет собой очерки истории искусства стран Западной Европы в средние века. Сюда были приглашены наиболее образованные люди тогдашней Европы.
75309. Международные связи в Западной Европе в XI-XV веков 40.5 KB
  Однако международные отношения этого периода не приняли еще достаточно регулярного характера: не было постоянных послов и дипломатических представительств не сложилось еще и международное право; само это понятие в целом едва ли применимо к этому времени развивались лишь отдельные его элементы и прежде всего право войны и морское право например Барселонское морское право оформившееся в XII в. Однако неожиданно монголотатары основательно истощенные к этому времени героическим сопротивлением Руси повернули в степи Причерноморья и...
75310. Возникновение, сущность и эволюция средневекового государства 34.5 KB
  Возникновение сущность и эволюция средневекового государства. Процесс образования централизованного феодального государства в России имел в своей основе те же общие закономерности исторического развития что и процесс образования централизованных феодальных государств в странах Западной Европы. Формы феодального государства были различными но классовая его сущность оставалась одна и та же. Характеризуя основные черты государства в средние века В.
75311. Происхождение термина «средние века» 28 KB
  Происхождение термина средние века. Термин средние века перевод с латинского выражения medium evum средний век 1 был впервые введен итальянскими гуманистами. С позиций высоких достижений культуры Возрождения средние века им виделись как период одичания и варваризации античного мира как время испорченной кухонной латыни. Келлер ввел термин средние века в общую периодизацию всемирной истории разделив ее на античность средневековье и новое время.