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.


 

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

25217. Кант і Гегель про джерело діалектичних суперечностей 30 KB
  Причина поняття абсолютного нескінченного належить світу речей в собі теза застосовується до світу досвіду де наявне лише скінченне обумовлене та скінчене. В діалектиці Гегеля поняття антиномії було перетворене в поняття протирічча що синтетично вирішується. Гегель намагався показати що походження багатоманітного з єдиного може бути предм етом раціонального пізнання інтрументом якогоє логічне мислення основною формою поняття. Оскільки поняття з сомого початку є тотожністю протилежностей то саморозвитток поняття підкоряється...
25218. Інтенціональність як універсальна характеристика свідомості 22.5 KB
  Інтенціональність як універсальна характеристика свідомості Інтенціональність означає напруженість спрямованість. Інтенційність традиційно вважається характеристикою свідомості. Інтенційність підкреслює цілісність свідомості. Не буває свідомості самої по собі.
25219. Типологія знання. Особливості наукового пізнання 25 KB
  Особливості наукового пізнання. Знання форма духовного засвоєння результатів пізнання процесу відображення дійсності що характеризується усвідомленням їх істинності. Рефлексія відображення термін для позначення такої риси людського пізнання як дослідження самого пізнавального акту діяльності самопізнання що дає змогу розкрити специфіку духовного світу людини. пізнання наук.
25220. Поняття розсудку та розуму в філософії Канта 27.5 KB
  Поняття розсудку та розуму в філософії Канта Вчення про розсудок і розсум Кант викладає в €œКритиці чистого розуму € в частині €œтрансцендентальна логіка€. Проблема розсуду розглядається Кантом в розділі трансцендентальна аналітика а розуму в трансцендентальній діалектиці. Хоча чуттєвість і мислення зовсім різні пізнавальні здібності проте знання може виникнути тільки завдяки поєднанню чуттєвості і розуму. Поняття розуму трансцендентальні ідеї.
25221. САМОСВІДОМІСТЬ 37.5 KB
  Відокремлюючи сутності від даностей за допомогою мислення у східній традиції відстороняючись від миру Я у розумінні простраивает суб'єктивне відношення до предмета іншому й собі як рефлексирование переінтерпретацію й реорганізацію значеннєвих структур свого буття у східній традиції знімаючи суб'єктивне й інші прив'язки до зовнішнього миру а тим самим і самою можливістю Я . до явного але не через роботу із предметними втримуваннями неясними або навпаки самоочевидними що є проблема й завдання когнітивних практик стратегій...
25222. Самосвідомість в житті людини та суспільства 29.5 KB
  Самосвідомість в житті людини та суспільства Самосвідомість це пізнання і оцінкам людини самої себе як мислячого і діяльнісного субкту. Самосвідомість невіємна с торона свідомості виражає данність субєктивної реальності свідомості самому субєкту. Самосвідомість передбачає емоційноціннісне і діяльніснорегулятивне відношення до себе. Самосвідомість проходить ряд етапів у своєму розвитку: 1 домовленневий рівень усвідомлення своєї фізичної самототожності меж свого тіла; 2 усвідомлення себе як субєкта дії ус відомлення своїх...
25223. Платон. «Парменід»: основні ідеї 22 KB
  Парменід: основні ідеї Головне питання твору: що є Єдине Це питання тісно повязане з розумінням Платона буття та світу ідей. Буття для Платона вічне незмінне недоступне чуттєвому сприйняттю і відкривається лише розумовому пізнанню. Буття множинне. Це можливе завдяки Єдинему яке за Платоном не співпадає з розумінням буття.
25224. Розвиток уявлень про природу категорій в історії філософії 29 KB
  Розвиток уявлень про природу категорій в історії філософії Категорії форма узагальнення понять фундаментальні поняття що формують умови можливості досвідного знання і мають апріорний характер універсальні форми синтезу знання Аристотель 10 категорій опис та визначення: субстанція кількість якість відношення місце час положення стан дія страждання схеми висловлювань про суще Метафізичні категорії онтологічна характеристика буття Метафізика€ Арістотеля Стоїки звуження вчення про категорії Аристотеля до вчення про роди...
25225. Поняття духу в філософії (Гегель, Шелер, Бердяєв). Цілераціональна і цінніснораціональна дія 30.5 KB
  Поняття духу в філософії Гегель Шелер Бердяєв. Цілераціональна і цінніснораціональна дія Поняття духу є центральним у філософії Гегеля. Сутність духу в самосвідомості самопізнання. Першопричина Абсолютний Дух Абсолютна ідея діяльність абсолютної ідеї мислення ціль самопізнання Протиставлення: Душа Дух звязок через мислення Душа має здатність сходження на рівень Духу 3 стадії розвитку Духу: субєктивний індивід дух замкнений в собі відособлений від зовнішнього світу антропологія феноменологія психологія практичний...