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.


 

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

2582. Статика и кинематика твердого тела 397.78 KB
  На схеме показаны три способа закрепления бруса, ось которого – ломаная линия. Задаваемая нагрузка и размеры во всех случаях одинаковы. Определить реакции опор для того способа закрепления бруса, при котором реакция YA имеет наименьший модуль. ...
2583. Документооборот на предприятии 520 KB
  Понятие документа, виды документов и их классификация. Состав и структура документов. Атрибуты документов. Документ (документированная информация) - зафиксированная на материальном носителе информация с реквизитами, позволяющими ее идентиф...
2584. Эвтаназия. Право выбора. Урок 167.43 KB
  Тема: Эвтаназия. Тип урока: урок - проблема. Вид урока: урок - диспут. Цель: обсудить с учащимися понятие Эвтаназия, историю возникновения; обсудить эвтаназию как проблему легкой смерти. Задачи:  Раскрыть содержание понятие...
2585. Облік у зарубіжних країнах 134.34 KB
  Навчальну програму з дисципліни Облік у зарубіжних країнах створено на основі освітньо-професійної програми підготовки бакалавра, спеціаліста і магістра Облік і аудит. Мета дисципліни Облік у зарубіжних країнах...
2586. Основні положення нормативно-правового регулювання питань електронного цифрового підпису в Україні 128.5 KB
  Метою лекції є вивчення основних положень нормативно-правового регулювання процесу створення, впровадження та експлуатації систем цифрового підпису та електронного документообігу в Україні. Під час розгляду навчальних питань звертається увага на...
2587. Предпринимательская производственная деятельность предприятия сервиса 2.17 MB
  Тема 1. Характеристика предпринимательства. Предпринимательство — это особый вид экономической активности, (под которой понимается целесообразную деятельность, направленная на извлечение прибыли), которая основана на самостоятельной инициативе,...
2588. История философии 670.39 KB
  Тема: Философия: смысл и предназначение План Предмет философии. Происхождение слова философия. Основные проблемы философии. Философия как мировоззрение. Типы мировоззрения. Функции философии в культуре. 1. Предмет фил...
2589. Психология человека 1.71 MB
  Содержание Часть 1. Психология человека – составная часть научного человекознания  Психология человека Историческое развитие представлений предмете психологии человека.Основные направления психологии человека как науки Ча...
2590. Стратегический менеджмент. Теории стратегического планирования 726.59 KB
  Классическая теория стратегического планирования Развитие стратегического менеджмента Основные положения разработки стратегии  Виды стратегии. Развитие стратегического менеджмента В развитии стратегического менеджмента можно выделить...