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.


 

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

6263. Забезпечення ефективного планування та організації освітнього процесу дошкільного навчального закладу 80.82 KB
  Забезпечення ефективного планування та організації освітнього процесу дошкільного навчального закладу. План Забезпечення ефективного планування та організації освітнього процесу дошкільного навчального закладу. Особливості ос...
6264. Методы принятия управленческих решений в условиях определенности 133 KB
  Методы принятия управленческих решений в условиях определенности Введение. Принятие решений в менеджменте Принятие решений - особый вид человеческой деятельности, направленный на выбор наилучшего способа достижения поставленной цели. Другими сл...
6265. Оптимизационные методы принятия управленческого решения в условиях определенности 229.5 KB
  Оптимизационные методы принятия управленческого решения в условиях определенности Содержание Управленческие решения в однокритериальных задачах. Построение экономико-математической модели. Математическая модель задачи линейного про...
6266. Симплексный метод принятия оптимального управленческого решения 113 KB
  Симплексный метод принятия оптимального управленческого решения Содержание Виды математических моделей ЗЛП. Идея симплексного метода нахождения оптимального решения. Алгоритм симплексного метода. Нахождение оптимального решен...
6267. Управленческие решения в задачах распределительного типа 233.5 KB
  Управленческие решения в задачах распределительного типа Содержание Примеры распределительных задач: транспортная и задача о назначениях. Постановка транспортной задачи и ее математическая модель. Методы построения плана перевозок Метод ...
6268. Управленческие решения в задачах финансового менеджмента. Схема простых процентов 130.5 KB
  Управленческие решения в задачах финансового менеджмента. Схема простых процентов Содержание Математическое понятие процента. Основные понятия финансовой математики. Основные принципы финансового анализа Принятие решений в финансовых...
6269. Управленческие решения в финансовом менеджменте. Подсчет сложных процентов 229.5 KB
  Управленческие решения в финансовом менеджменте. Подсчет сложных процентов Содержание Начисление сложных годовых процентов Сравнение наращения по простым и сложным процентам Наращение по сложным процентам при нецелом числе лет...
6270. Управленческие решения в конфликтных ситуациях 219.5 KB
  Управленческие решения в конфликтных ситуациях Содержание Теория игр как основа моделирования конфликтных ситуаций. Антагонистические игры (принцип минимакса, седловой элемент, цена игры, решение игры). Доминирование стратегий игро...
6271. Принятие решений в условиях риска 161 KB
  Принятие решений в условиях риска Неопределенность и риск при разработке и принятии решений. Принятие управленческого решения в условиях риска. Статистические игры (игры с природой) Риск статистика в игре с природой К...