РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ
создание документов онлайн
Документы и бланки онлайн

Обследовать

Администрация
Механический Электроника
биологии
география
дом в саду
история
литература
маркетинг
математике Физика информатики химия
медицина
музыка
образование
психология
разное
художественная культура
экономика





















































РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ

математике



Отправить его в другом документе Tab для Yahoo книги - конечно, эссе, очерк Hits: 1364



дтхзйе дплхнеофщ

РАБОЧИЕ И УЧЕБНЫЕ МАТЕРИАЛЫ
Математическая модель при отсутствии сопротивления внешней среды
НЕОПРЕДЕЛЕННЫЙ ИНТЕГРАЛ
Функциональные последовательности и ряды (продолжение)
Неодновременное поступление работ
Система n линейных уравнений с n переменными. Метод обратной матрицы и формулы Крамера.
Скалярное произведение и его свойства
Интеграл Лебега
Мода. Медиана.
ЭРМИТОВЫ ФОРМЫ В УНИТАРНОМ ПРОСТРАНСТВЕ
 

РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ

Одной из важнейших прикладных задач численных методов является точное или приближенное решение систем линейных уравнений. Многие математические модели приводят к данной задаче непосредственно, но еще чаще к данной задаче приходят после применения каких-либо методов решения более сложных задач. Отметим лишь один самый важный класс моделей, приводящий к системам линейных уравнений – метод сеток для решения систем уравнений в частных производных. Очень большое количество задач естественных наук (физика, аэро- и гидродинамика, химия, биология) на стадии построения математических м 919g66jj оделей происходящих процессов приводят к уравнениям или системам уравнений с частными производными. Для нахождения их приближенных решений применяется метод сеток, в результате которого и получаются системы линейных уравнений. Отличительной особенностью таких систем являются их очень большие размеры (десятки и сотни тысяч уравнений и неизвестных).

Постановка задачи и ее качественное исследование.

Рассмотрим систему m линейных уравнений с n переменными:

                (7.1)

Систему (7.1) можно записать короче в виде одного матричного уравнения AX=B,

где Х -столбец длины n, B -столбец длины m, А -матрица размерами mхn.

TEOРЕМА 1. Если ранг матрицы А совпадает с рангом расширенной матрицы (А|B), то в этом случае существует решение системы (7.1) и наоборот.

ТЕОРЕМА 2. В случае, когда количество уравнений совпадает с числом неизвестных и определитель A отличен от 0, существует единственное решение системы(7.1).



m=n и det(А)<>0 => решение (7.1) существует и единственно.

Если n>m, то решений (7.1) обычно бесконечное множество (линейное пространство размерности n-rang(A)). Если m>n, то обычно решений нет.

Упражнение 7.1. Приведите пример несовместной системы, у которой m<n.

Упражнение 7.2. Приведите пример совместной системы, у которой m>n.

Далее мы ограничимся рассмотрением частного случая: m=n и det(А)<>0, т.е. случай, когда решение существует и единственно, хотя метод Гаусса, например, носит универсальный характер.

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

К прямым методам относятся, кроме метода Гаусса, метод квадратного корня для симметричных матриц (или компакт-метод для произвольных), метод Крамера. Последний метод обычно изучается в теории систем линейных уравнений в виду возможности кратко записать решение системы. Пусть D-определитель квадратной матрицы А системы линейных уравнений: D=det(A)¹0. Пусть D(i)-определитель матрицы, у которой на i-ом месте находится столбец В, а остальные столбцы совпадают с соответствующими столбцами матрицы А. Тогда координаты вектора решения находятся по формулам: Х(i)=D(i)/D.

Упражнение 7.3. Определите по формулам Крамера решение системы и проверьте его:

Метод Гаусса

(метод последовательного исключения переменных)

Матрица называется верхнетреугольной, если ниже главной диагонали все элементы равны нулю, т.е. aij=0 при i>j. Аналогично, матрица называется нижнетреугольной, если все элементы выше главной диагонали (i<j) равны 0. Матрица называется диагональной, если только на главной диагонали (i=j) стоят ненулевые элементы. Метод Гаусса решения систем линейных уравнений состоит из двух этапов: прямого хода и обратного хода.

Прямой ход.

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

Рассмотрим k-ый шаг прямого хода. На k-ом шаге матрица системы имеет вид:

11       а12        …        а1k        …        a1n | b1)

(0         a22        …        a2k        …        a2n | b2)

 (0        …        …        …        …        …        )

(0         0          …        akk        …        akn | bk)

 (0        …        …        …        …        …        )

(0         0          …        ank        …        ann | bn)

Осталось n-k+1 неизвестных. Чтобы удалить х(k) из последней строчки, например, надо из нее вычесть k-ую строчку с таким коэффициентом, чтобы получить на месте аnk ноль. Для этого коэффициент должен быть равен cnk=ank/akk. Элемент аkk называется разрешающим элементом k-ого шага и должен быть отличен от 0.

Формулы прямого хода

cmk=amk/akk                       где     1<=k<n

bm=bm-cmkbk,                            k<m<=n

aml=aml-cmkakl,                           k<=l<=n

Обратный ход

Последовательное вычисление значения неизвестных xn, xn-1,..., х1 (именно в таком порядке) для полученной после прямого хода верхнетреугольной системы называется обратным ходом.

Формулы обратного хода.

           ,откуда получаем:

для k=n,n-1,…,1.

Ручные вычисления по методу Гаусса.

В процессе ручных вычислений по методу Гаусса заполняется таблица, которая состоит из нескольких разделов, соответствующих определенным этапам вычислений. В ней вводится столбец s- сумма всех коэффициентов в строке, столбец s- контрольный столбец (на нулевом шаге он заполняется из столбца s, а затем преобразуется вместе со строками по той же формуле, причем, сравнивая его со столбцом s, мы проверяем правильность вычислений, поскольку данные столбцы должны совпадать). На каждом следующем шаге прямого хода в таблице уменьшается как количество уравнений (т.к. на k-м шаге мы меняем только последние n-k уравнений), так и количество неизвестных. При этом один из пустых столбцов таблицы (там должны были бы стоять только нули) мы используем для записи коэффициентов cmk, на которые домножаем k–ю строку перед вычитанием из m–й.



Пример. Решить систему:

Таблица при ручных вычислениях имеет вид:

___________________________________________

  N шага   |     Матрица А  | Св.член |   s   |   s

_______ _|_____________|________|____|________

                 |   3    -1    0       |    1           |   3   |    3

     0          |  -2     1    1       |    0           |   0   |    0

                 |   2    -1    4       |    0           |   5   |    5

 ________|_  ___________|________|_ ___|_______

                 |-2/3   1/3    1     |   2/3         |   2   |    2

     1          | 2/3  -1/3    4     |  -2/3        |   3    |    3

______ __|_____________|________|_____|_______

     2          |        -1    5        |    0           |   5   |    5

________|_____________|_________|____|_______

           |              х3    =    0    |

           |         х2         =    2    |

           |   х1               =    1    |

Регуляризация решения

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

Задача 7.4. Докажите, что в невырожденных системах не может встретиться случай, когда и разрешающий элемент, и все элементы столбца ниже него на каком-то шаге окажутся равными нулю одновременно.

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

___________________________________________

      |    1.2357   |    2.1742   |   -5.4834   |   -2.0735

   0 |    6.0696   |   -6.2163   |   -4.6921   |   -4.8388

      |    3.4873   |    6.1365   |   -4.7483   |    4.8755

___|_________|_________|_________|__________

   1  |    4.919    |   -16.895   |    22.242   |    5.3462

       |    2.8221  |    0.0007   |    10.727   |    10.727

___ |__ ______|_________|_________|__________

   2  |                 |   0.41E-04 |    10.728   |    10.727

___ |_________|_________|_________|__________

       |                                  x3     =   0.99991

       |                    x2                   =   0.99994

       |     x1                                  =   0.99968

___ |_______________________________________

Правильный ответ: х1=1, х2=1, х3=1

Теперь поменяем местами 2-е и 3-е уравнения:

__________________________________________

       |   1.2357    |    2.1742   |  -5.4834    |  -2.0735

  0   |   3.4873    |    6.1365   |  -4.7483    |   4.8755

       |   6.0696    |   -6.2163   |  -4.6921    |  -4.8388

___|_________|__________|_________|__________

  1   |   2.8221    |    0.0007   |   10.727    |   10.727

       |   4.919      |   -16.895  |   22.242    |   5.3462

___|_________|_________|_________|__________

  2   |                 |     24136   |   258930    |   258910

___|_________|_________|_________|___________

      |                                 x3      =   0.99992

      |                    x2                   =   1.4286

      |     x1                                  =   2.9021

___|________________________________________

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

Описание метода Гаусса для вырожденных систем.

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

·        либо мы видим, что полученная система несовместна, когда в одной из последних ненулевых строк все коэффициенты левой части равны 0, а свободный член – нет




·        либо система имеет бесконечное множество решений, которые можно получать следующим общим способом – задать произвольные значения всем «свободным» переменным, которые были пропущены в процессе исключения, т.е. «исключились сами по себе» и вычислить значения всех остальных переменных по формулам обратного хода.

Применения метода Гаусса.

Метод Гаусса является одним из эффективных методов решения различных задач линейной алгебры.

Нахождение определителя матрицы.

Исходную матрицу приводят к верхнетреугольному виду методом Гаусса, следя при перестановке строк за сменой знака определителя. После приведения определитель будет равен произведению элементов главной диагонали.

Нахождение обратной матрицы

Пусть А' - обратная матрица, т.е.  А*А'=Е. Для того, чтобы найти обратную матрицу, каждый столбец матрицы А' обозначим как неизвестный вектор Х(1),Х(2),….Тогда для  решения матричного уравнения А(Х(1)Х(2)...)=Е можно  N раз решить систему линейных уравнений методом Гаусса с неизвестным вектором Х(i) и правым столбцом – одним из столбцов единичной матрицы.

Второй метод нахождения обратной матрицы: выпишем матрицу (А|Е), в которой n строчек и 2n столбцов. Проделав прямой ход, получим                         (\ # # |   )

   (0 \ # | A`)

  (0 0 \ |   ),

где А` - промежуточная матрица                                         (\ # #)

Обратный ход заключается в том, что матрицу                 (0 \ #)               приводят

к единичной                                                                         (0 0 \)

В результате получим матрицу ( Е|А').

Нахождение ранга матрицы.

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

Определение совместности системы.

Поскольку совместность системы означает совпадение рангов матрицы А исходной системы и расширенной матрицы (А|B), то проще всего поступить аналогично предыдущему пункту. Берем расширенную матрицу и приводим к ступенчатому виду. Если есть строки с нулевой левой частью и ненулевым свободным членом, то система несовместна, если нет – совместна.

Контрольные вопросы

1.      Какова общая постановка задачи решения систем линейных уравнений?

2.      Какие виды рангов определяются для матриц? Почему они равны? Что такое ранг матрицы?

3.      Сформулируйте условие существования решения и условие единственности решения.

4.      Что такое эквивалентное преобразование системы? Какие они бывают?

5.      Почему при добавлении к строке линейной комбинации других строк решение не меняется?

6.      Докажите, что при ручных вычислениях контрольный столбец должен совпадать со столбцом s

7.      С чем связана необходимость переставлять местами уравнения системы при решении?

8.      Как устроено множество решений общей системы линейных уравнений?

9.      Как определить базис пространства решений системы, зная  номера свободных переменных?

10.  Перечислите применения метода Гаусса при решении задач линейной флгебры.

Содержание лабораторной работы «Метод Гаусса»

1.Ответить на вопросы контролирующей программы.

2. Составить программу решения систем методом Гаусса, протестировать ее на контрольных примерах. Выполнить программу для своего варианта и записать ответы.

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

Содержание лабораторной работы «Применения метода Гаусса»

1. Составить, отладить и протестировать программу для решения одной из следующих задач:

·        найти определитель матрицы;

·        найти обратную матрицу;

·        найти ранг матрицы;

·        определить совместность системы;

·        решение системы при ручном счете;

·        решение общих систем методом Гаусса.

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