Министерство  образования Республики Беларусь

Учреждение  образования

«Белорусский  государственный университет информатики  и радиоэлектроники» 
 
 
 
 
 

Реферат 

по дисциплине:

«Основы информационных технологий»

Н а   т е м у :

«Прямые методы решения СЛАУ» 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

                                                       Выполнил:

                                                           Руденко М.В. 

                                                    

                                             
 
 
 
 
 
 
 
 
 
 
 
 

МИНСК 2011

 

Содержание

Введение……………………………………………………...……………………3

Метод Гаусса………………………………………………………………………4

Метод квадратного корня………………………………………………………...7

Метод вращений решения линейных систем……………………………………8

Заключение……………………………………………………………………….11

Список литературы………………………………………………………………12 
 
 

 

Введение

        Методы численного решения системы линейных уравнений делятся на две группы: прямые методы («точные») и итерационные методы.

        Прямыми методами называются методы, позволяющие получить решение  системы (1) за конечное число арифметических операций. К этим методам относятся метод Крамера, метод Гаусса, LU-метод и т.д.

        Итерационные методы (методы последовательных приближений) состоят в том, что решение  системы находится как предел последовательных приближений  при , где n номер итерации. При использовании методов итерации обычно задается некоторое малое число e>0 и вычисления проводятся до тех пор, пока не будет выполнена оценка . К этим методам относятся метод Зейделя, Якоби, метод верхних релаксаций и т.д.

        Следует заметить, что  реализация прямых методов на компьютере приводит к решению с погрешностью, т.к. все арифметические операции над  переменными с плавающей точкой выполняются с округлением. В зависимости от свойств матрицы исходной системы эти погрешности могут достигать значительных величин.

 

         Метод Гаусса

        Рассмотрим систему  линейных алгебраических уравнений (СЛАУ) [1,2]

        

,     (1)

        где - матрица , - искомый вектор, - заданный вектор. Будем предполагать, что определитель матрицы отличен от нуля, т.е. решение системы (1) существует.

        Запишем систему  Ax=f,  в развернутом виде                                               

        

        Метод Гаусса состоит  в последовательном исключении неизвестных  из этой системы. Предположим, что  . Последовательно умножая первое уравнение на и складывая с i-м уравнение, исключим из всех уравнений кроме первого. Получим систему

        

        

        Аналогичным образом  из полученной системы  исключим . Последовательно, исключая все неизвестные, получим систему треугольного вида

        

        Описанная процедура  называется прямым ходом метода Гаусса. Заметим, что ее выполнение было возможно при условии, что все  , не равны нулю.

        Выполняя последовательные подстановки в последней системе, (начиная с последнего уравнения) можно получить все значения неизвестных. 

             .

        Эта процедура получила название обратный ход метода Гаусса..

        Метод Гаусса может быть легко реализован на компьютере. При выполнении вычислений, как правило, не интересуют промежуточные значения матрицы А. Поэтому   численная реализация  метода  сводится  к преобразованию элементов массива размерности (m×(m+1)), где m+1 столбец содержит элементы правой части системы.

        Для контроля ошибки реализации метода используются так  называемые контрольные суммы. Схема  контроля основывается на следующем  очевидном положении. Увеличение значения всех неизвестных на единицу равносильно  замене данной системы контрольной системой, в которой свободные члены равны суммам всех коэффициентов соответствующей строки. Создадим дополнительный столбец, хранящий сумму элементов матрицы по строкам. На каждом шаге реализации прямого хода метода Гаусса будем выполнять преобразования и над элементами этого столбца, и сравнивать их значение с суммой по строке преобразованной матрицы. В случае не совпадения значений счет прерывается.

        Существует метод  Гаусса с выбором главного элемента по всей матрице. В этом случае переставляются не только строки, но и столбцы. Использование модификаций метода Гаусса приводит к усложнению алгоритма увеличению числа операций и соответственно к росту времени счета. Поэтому целесообразность выбора того или иного метода определяется непосредственно программистом.

        Выполняемые в методе Гаусса преобразования прямого хода, приведшие матрицу А системы к треугольному виду позволяют вычислить определитель матрицы

         .

        Метод Гаусса позволяет  найти обратную матрицу. Для этого необходимо решить матричное уравнение

         ,

        где Е- единичная матрица. Его решение сводится к решению m систем

        

        у вектора  j –я компонента равна единице, а остальные компоненты равны нулю.

Метод квадратного корня

 

            Метод квадратного корня по своему идейному содержанию близок к LU-методу. Основное отличие в том, что он дает упрощение для симметричных матриц.

        Этот метод основан  на разложении матрицы А в произведение

        

        где S–верхняя треугольная матрица с положительными элементами на главной

        

        

        Из условия (2) получаются уравнения

        

        Так как матрица  А симметричная, не ограничивая общности, можно считать, что в системе (3) выполняется неравенство i≤j. Тогда (3) можно переписать в виде

        

        

        

        В частности, при  i=j получится

        

        

    (4)

        Далее, при i<j получим

        

        По формулам (4) и (5) находятся рекуррентно все ненулевые   элементы матрицы S.

        Обратный ход метода квадратного корня состоит в  последовательном решении двух систем уравнений с треугольными матрицами.

        

        Решения этих систем находятся по рекуррентным формулам            

        

        

        Всего метод квадратного  корня при факторизации A=S^тS требует примерно операций умножения и деления и m операций извлечения квадратного корня.[1] 

        Метод вращений решения  линейных систем 

        Как и в методе Гаусса, цель прямого хода преобразований в этом методе–приведение системы  к треугольному виду последовательным обнулением поддиагональных элементов сначала первого столбца, затем второго и т.д.

        

        Умножим первое уравнение  исходной системы (1) на с₁ ,второе на s₁ и сложим их ; полученным уравнением заменим первое уравнение системы. Затем первое уравнение исходной системы умножаем на –s₁ , второе на c₁  и результатом их сложения заменим второе уравнение . Таким образом, первые два уравнения (1) заменяются уравнениями

        

         

        

        

        Отсюда  . Эти числа можно интерпретировать как косинус и синус некоторого угла (отсюда название метод вращения, каждый шаг такого преобразования можно рассматривать как вращение расширенной матрицы системы в плоскости обнуляемого индекса).

        В результате преобразований получим систему 

        

        где

         

        Далее первое уравнение  системы заменяется новым, полученным сложением результатов умножения  первого и третьего уравнений  соответственно на

        

        а третье–уравнением,  полученное  при сложении   результатов умножения тех же

        

        где

        

        Выполнив преобразование m-1 раз, придем к системе

        

              Вид  полученной системы такой же, как после первого этапа преобразований методом Гаусса. Эта система обладает следующим свойством: длина любого вектора-столбца (эвклидова норма) расширенной матрицы остается такой же, как у исходной матрицы. Следовательно, при выполнении преобразований не наблюдается рост элементов.

        Далее по этому же алгоритму преобразуется матрица

        

        и т.д.

        В результате m-1 этапов прямого хода система будет приведена к треугольному виду.

        

        Нахождение неизвестных  не отличается от обратного хода метода Гаусса.

        Всего метод вращения требует примерно операций умножения и деления.

 

        Заключение 

            Один из важных факторов предопределяющих выбор того или иного метода при решении конкретных задач, является вычислительная эффективность метода.

   Один  из основных недостатков метода Гаусса связан с тем, что при его реализации накапливается вычислительная погрешность. Для больших систем порядка m число действий умножений и делений близко к , решение СЛАУ методом квадратного корня требует и m операций извлечения корней. Метод вращения предполагает вчетверо больше операций умножения, чем в методе Гаусса. При больших значениях размерности m, можно сказать, что вычислительные затраты на операции умножения и деления в методе Гаусса составляют величину , в методе квадратных корней , в методе вращений .