Просмотр

Материал из MachineLearning.

У вас нет прав на выполнение этой операции по следующим причинам:

• Запрошенное действие могут выполнять только участники из групп emailconfirmed, Администраторы.
• Вы должны подтвердить ваш адрес электронной почты перед правкой страниц. Пожалуйста, введите и подтвердите ваш адрес эл. почты на странице настроек.

Вы можете просмотреть и скопировать исходный текст этой страницы:

== Постановка задачи == Дана [[система линейных алгебраических уравнений]] (СЛАУ), состоящая из <tex>n</tex> уравнений с <tex>n</tex> неизвестными : {{eqno|1}} <tex> \left\{\begin{array}{lcr} a_{11}x_1+\ldots+a_{1n}x_n &=& b_1 \\ \\ \cdots & & \\ \\ a_{n1}x_1+\ldots+a_{nn}x_n &=& b_n \\ \end{array} \right. \quad \Longleftrightarrow \quad A\vec{x}=\vec{b}, \quad A=\left( \begin{array}{ccc} a_{11} & \ldots & a_{1n}\\ \\ \cdots & & \\ \\ a_{n1} & \ldots & a_{nn} \end{array}\right),\quad \vec{b}=\left( \begin{array}{c}b_1 \\ \\ \vdots \\ \\ b_n \end{array} \right). </tex> Предполагается, что существует единственное решение системы, то есть <tex>detA \neq 0</tex>. В данной статье будут рассмотрены причины погрешности, возникающей во время решения системы с помощью метода Гаусса, способы выявления и ликвидации(уменьшения) этой погрешности. == Описание метода == Процесс решения системы линейных уравнений {{eqno|2}} <center><tex>\sum_{j=1}^n a_{ij}x_{j} = b_{i}, \qquad i=1,\ldots,n,</tex></center> по методу Гаусса состоит из 2х этапов: * Прямой ход *: Система {{eqref|2}} приводится к треугольному виду :: 1. Предполагаем, что <tex>a_{11} \neq 0</tex> . Тогда первое уравнение системы {{eqref|2}} делим на коэффициент <tex>a_{11}</tex>, в результате получаем уравнение <center><tex>x_{1}+\sum_{j=2}^n a_{ij}^{1}x_{j} = b_{i}^{1}</tex></center>. ::Затем из каждого из оставшихся уравнений вычитается первое, умноженное на соответствующий коэффициент <tex>a_{i1}</tex>. В результате система преобразуются к виду: <center><tex>\left( \begin{array}{ccc} 1 & a_{12}^{1} & \ldots & a_{1n}^{1}\\ \\ 0 & a_{22}^{1} & \ldots & a_{2n}^{1}\\ \\ \vdots & \vdots & \ddots & \vdots\\ \\ 0 & a_{n2}^{1} & \ldots & a_{nn}^{1} \end{array}\right) \left( \begin{array}{c}x_1 \\ \\ x_2 \\ \\ \vdots \\ \\ \\ x_n \end{array}\right) = \left( \begin{array}{c}b_1^1 \\ \\ b_2^1 \\ \\ \vdots \\ \\ b_n^1 \end{array}\right)</tex></center> :: 2. В предположении, что <tex>a_{22}^1 \neq 0</tex>, делим второе уравнение на коэффициент <tex>a_{22}^1</tex> и исключаем неизвестное <tex>x_2</tex> из всех последующих уравнений и т.д. :: 3. Получаем систему уравнений с треугольной матрицей: {{eqno|3}} <center><tex>\left( \begin{array}{ccc} 1 & a_{12}^n & \ldots & a_{1n}^n\\ \\ 0 & 1 & \ldots & a_{2n}^n\\ \\ \vdots & \vdots & \ddots & \vdots\\ \\ 0 & 0 & \ldots & 1 \end{array}\right) \left( \begin{array}{c}x_1 \\ \\ x_2 \\ \\ \vdots \\ \\ \\ x_n \end{array}\right) = \left( \begin{array}{c}b_1^n \\ \\ b_2^n \\ \\ \vdots \\ \\ b_n^n \end{array}\right)</tex></center> * Обратный ход *: Непосредственное определение неизвестных :: 1. Из <tex>n-</tex>го уравнения системы {{eqref|3}} определяем <tex>x_{n}:\: \quad x_n=b_n^n</tex> :: 2. Из <tex>(n-1)-</tex>го - определяем <tex>x_{n-1}:\: \quad x_{n-1}=b_{n-1}^n-a_{(n-1)n}^n x_n</tex> и т.д. == Анализ метода == Данный метод относится к классу прямых методов решения системы уравнений, а это значит, что за конечное число шагов можно получить точное решение, при условии, что входные данные ( матрица <tex>A</tex> и правая часть уравнения - <tex>b</tex>) заданы точно и вычисление ведется без округлений. Для получения решения требуется <tex>\frac{m^3}{3}+ m^2 - \frac{m}{3}</tex> умножений и делений, то есть порядка <tex>O(\frac{m^3}{3})</tex> операций. Условия, при которых метод выдает точное решение, на практике не выполнимы - неизбежны как ошибки входных данных, так и ошибки округления. Тогда встает вопрос: насколько точное решение можно получить, используя метод Гаусса, насколько метод корректен? Определим устойчивость решения относительно входных параметров. Наряду с исходной системой {{eqref|1}} рассмотрим возмущенную систему: <center><tex>(A + \delta A)(x + \delta x)=b + \delta b</tex></center> Пусть введена некоторая норма <tex>|| . ||</tex>. <tex>CondA=|| A || * || A^{-1}||</tex> - называется числом обусловленности матрицы <tex>A</tex>. Возможны 3 случая: 1) <tex>\delta A = 0 , \quad \delta b \neq 0</tex> : :<tex>\frac{||\delta x||}{||x||} &\leq& Cond A \frac{||\delta b ||}{|| b ||}</tex> 2) <tex>\delta A \neq 0 , \quad \delta b = 0</tex> : :<tex><tex>\frac{||\delta x||}{||x||} \leq Cond A \frac{||\delta A ||}{|| A ||}</tex> 3) <tex>\delta A \neq 0 , \quad \delta b \neq 0</tex> : :<tex><tex>\frac{||\delta x||}{||x||} \leq \frac{Cond A}{1-Cond A\frac{||\delta A ||}{|| A ||}}(\frac{||\delta A ||}{|| A ||}+ \frac{||\delta b ||}{|| b ||})</tex> Число обусловленности матрицы <tex>A</tex> всегда <tex>\geq 1</tex>. Если оно велико ( <tex>Cond A \approx 10^k k \geq 2</tex> ) , то говорят, что матрица <tex>A</tex> плохо обусловлена. В этом случае малые возмущения правых частей системы {{eqref|1}}, вызванные либо неточностью задания исходных данных, либо вызванные погрешностями вычисления, существенно влияют на решение системы. Грубо говоря, если погрешность правых частей <tex>10^{-l}</tex> , то погрешность решения будет <tex>10^{-l+k}</tex> . Проиллюстрируем полученные результаты на следующем числовом примере: Дана система :<tex>\left\{\begin{array}{lcr}5x_1+7x_2 &=& 12 \\ \\ 7x_1+10x_2 &=& 17 \\ \end{array} \right.</tex> Она имеет решение <tex>(1, \quad 1)</tex>. Теперь рассмотрим возмущенную систему: :<tex>\left\{\begin{array}{lcr}5x_1+7x_2 &=& 12.075 \\ \\ 7x_1+10x_2 &=& 16.905 \\ \end{array} \right.</tex> Решением такой системы будет вектор <tex>(2.415, \quad 0)</tex>. При совсем малом возмущении правой части получили несоизмеримо большое возмущение решения. Объяснить такую "ненадежность" решения можно тем, что матрица <tex>A</tex> почти вырожденная: прямые, соответствующие двум уравнениям, почти совпадают, что видно на графике: [[Изображение:Слау.jpg|left|thumb|Геометрическое представление системы двух линейных алгебраических уравнений, которая является почти вырожденной. Прямые, соответствующие двум уравнениям, почти совпадают.]] Такой результат можно было предвидеть в силу плохой обусловленностью матрицы <tex>A = \left( \begin{array}{ccc} 5 & 7\\ \\ 7 & 10 \end{array}\right)</tex> : <tex>Cond A = 17^2</tex> <ref>Здесь и далее в числовых примерах будем рассматривать метрику <tex>||.||_1</tex> : <tex>||x||_1=\sum_{i=1}^n | x_i |, \quad || A ||_1 = \max_{j} \left( \sum_{i=1}^n | a_{ij} |\right)</tex></ref> Вычисление <tex>Cond A </tex> является достаточно сложным, сравнимо с решением всей системы, поэтому для оценки пограшности применяются более грубые, но простые в реализации методы. == Способы оценки ошибок == :1) <u>'''Контрольная сумма:'''</u> обычно применяется для предупреждения случайных погрешностей в процессе вычисления без помощи компьютеров. Составляем контрольный столбец <tex>a_{n+1} = \left( a_{1,n+1}, \ldots, a_{n, n+1}\right)</tex>, состоящий из контрольных элементов системы: :<tex>a_{i, n+1} = \sum_{j=1}^n a_{i, j} + b_i</tex> При преобразовании уравнений над контрольными элементами производятся те же операции, что и над свободными членами уравнеий. В результате этого контрольный элемент каждого нового уравнения должен равняться сумме коэффициентов этого уравнения. Большое расхождение между ними указывает на погрешности в вычислениях или на неустойчивость алгоритма вычислений по отношению к вычислительной погрешности. :2) <u>'''Относительная погрешность известного решения'''</u> позволяет без существенных дополнительных затрат получить суждение о погрешности решения. Задается некоторый ветор <tex>z</tex> с компонентами, имеющими по возможности тот же порядок и знак, что и компоненты искомого решения <ref>Часто из-за отсутствия доплнительной информации берут <tex>z=\left(1, \ldots, 1\right)</tex></ref>. Вычисляется вектор <tex>c=Az</tex>, и на ряду с исходной системой уравнения решается система <tex>Az=c</tex>. Пусть <tex>x'</tex> и <tex>z'</tex> - реально получаемые решения этих систем. Суждение о погрешности <tex>x-x'</tex> искомого решения можно получить, основываясь на гипотезе: относительные погрешности при решении методом исключения систем с одной и той же матрицей и различными правыми частями, которыми являются соответственно величины <tex>\frac{||x-x'||}{||x'||}</tex> и <tex>\frac{||z-z'||}{||z'||}</tex>, отличаются не в очень большое число раз. :3) <u>'''Изменение масштабов'''</u> - прием, применяющийся для получения представления о реальной величине погрешности, возникающей за счет округлений при вычислениях. Наряду с исходной системой тем же методом решается система :<tex>\left( \alpha A\right)x' = \beta b</tex>, где <tex>\alpha</tex> и <tex>\beta</tex> - числа Если бы не было погрешности округления, то выполнялось бы равенство для решений исходной и масштабированной систем: <tex>x=\alpha \beta^{-1}x'</tex>. Поэтому при <tex>\alpha</tex> и <tex>\beta</tex>, не являющихся степенями двойки, сравнение векторов <tex>x</tex> и <tex>\alpha \beta^{-1}x'</tex> дает представление о величине вычислительной погрешности <ref>Например, можно взять <tex>\alpha=\sqrt{2}, \quad \beta=\sqrt{3}</tex></ref> == Улучшение метода исключения Гаусса== === Выбор главного элемента === === Итеративное улучшение результата === == Программа, реализующая метод на C++ == == Рекомендации программисту == <references/> == Список литературы == * ''Н.С.Бахвалов, Н.П.Жидков, Г.М.Кобельков'' Численные методы == Внешние ссылки == *[http://ru.wikipedia.org/wiki/%D0%9E%D0%B1%D1%80%D0%B0%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D1%80%D0%B8%D1%86%D0%B0 Обратная матрица] == См. также == * [[Практикум ММП ВМК, 4й курс, осень 2008|Практикум ММП ВМК, 4й курс, осень 2008]] {{stub}} [[Категория:Решение СЛАУ]] [[Категория:Учебные задачи]]

• Шаблон:Eqno
• Шаблон:Eqref
• Шаблон:Stub
• Шаблон:Заготовка

Возврат к странице Методы исключения Гаусса.