Решение систем линейных алгебраических уравнений прямые методы. Дана система линейных алгебраических уравнений. Требуется найти решение системы



Скачать 231.79 Kb.
Дата28.11.2012
Размер231.79 Kb.
ТипРешение
Лабораторная работа № 2.3

РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

ПРЯМЫЕ МЕТОДЫ.

Дана система линейных алгебраических уравнений

.

Требуется найти решение системы.

В дальнейших рассмотрениях вектор-столбец правых частей удобнее рассматривать как - й столбец расширенной матрицы: . При ссылках на строки мы будем иметь в виду строки расширенной матрицы.

Метод Гаусса (метод исключений).

Будем решать систему методом исключений, путем сведения матрицы системы к треугольной.

Выполняем исключения в первом столбце:

- если , найдем такую строку i , для которой . Переставим строки 1 и i;

- строку 2 заменим линейной комбинацией строк: строка - строка ; в результате получим ;

- строку 3 заменим линейной комбинацией строк: строка - строка и т.д.; строку i заменяем комбинацией строка - строка .

Завершив исключения в столбце 1, переходим к столбцу 2 и т.д. После исключения в столбце мы получим систему с треугольной матрицей.

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

Модифицируем метод:

- строку 2 заменим комбинацией строка 2 - строка 1*u, где

gif" name="object18" align=absmiddle width=73 height=21>;

- строку 3 заменим комбинацией строка 3 - строка 1*u, где

и д.

Теперь число умножений сократилось вдвое.

Заметим, что вместо вычисления множителя u для каждой строки мы можем строку 1 разделить на и затем из строки вычитать строку 1, умноженную на . Число операций умножения - деления при этом не изменится.

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

- пусть при вводе коэффициентов мы допустили погрешность, не превосходящую ;

- пусть все исключения выполняются только путем вычитания строк (без умножения на множитель u) и все операции выполняются точно.

Тогда: после исключения в столбце 1 погрешность коэффициентов матрицы может достигать величины , после исключения в столбце 2 - величины и т.д. После исключения в столбце погрешность коэффициента может достигать величины .

Полученная грубая оценка характеризует скорость нарастания погрешности - если порядок системы увеличивается на 10, вычислительная погрешность может увеличиться в 1000 раз.

Для того, чтобы компенсировать этот недостаток, будем поступать следующим образом:

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

;

- строки и меняем местами.

В этом случае

.

Таким образом, в процессе исключений (строка заменяется суммой строка i u*строка k) строку k и накопленную вычислительную погрешность мы будем умножать на множитель, не превосходящий 1.

Элемент называется главным (или ведущим) элементом, метод исключения - методом Гаусса с выбором главного (ведущего) элемента.

Поиск главного элемента позволяет нам решить еще одну задачу: если , то определитель матрицы системы = 0, система не имеет единственного решения. Ввиду наличия вычислительной погрешности условие следует заменить условием . При выполнении этого условия процесс вычислений прекращается.

Схема алгоритма исключения приобретает вид

Метод Гаусса с выбором главного элемента.

Вход: расширенная матрица системы линейных алгебраических уравнений.

Выход: матрица системы, приведенная к треугольному виду.

Для выполняем исключение в столбце k:

ищем главный элемент, пусть ;

если ,то выход - матрица системы вырожденная;

переставляем строки g и k ;

полагаем строка k = строка k /;

для полагаем

строка i = строка i – aik*строка k.

Все операции над строками следует начинать со столбца k - элементы в столбцах равны 0.

По завершении исключения вычисляем решение системы (обратный ход):

- если , то матрица системы вырождена, выход;

- полагаем ;

- для полагаем

.

Метод Жордана. Будем проводить исключение коэффициентов при неизвестных не только под, но и над главной диагональю. Исключение будем проводить для всех столбцов . В результате по завершении исключения матрица системы будет сведена к единичной матрице, на месте вектор-столбца правых частей мы получим решение системы. Обратный ход не требуется.

Такой вариант метода Гаусса называется методом Жордана (схемой Жордана).

Подчеркнем: главный элемент в столбце, как и ранее, выбирается начиная с главной диагонали и ниже - перестановка строк k и g при g
Схема алгоритма исключения приобретает вид

Метод Жордана с выбором главного элемента.

Вход: расширенная матрица системы линейных алгебраических уравнений.

Выход: решение системы в n+1 столбце расширенной матрицы.

Для выполняем исключение в столбце k:

ищем главный элемент, пусть ;

если ,то выход - матрица системы вырожденная;

переставляем строки g и k ;

полагаем строка k = строка k /;

для полагаем

строка i = строка i – aik*строка k.

Все операции над строками следует начинать со столбца k - элементы в столбцах равны 0.

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

Рассмотрим особенности работы алгоритмов Гаусса и Жордана при выборе главного элемента "по всей матрице". Пусть при исключении в столбце k мы имеем



Для того, чтобы элемент оказался на главной диагонали, следует переставить строки k и g и столбцы k и h. При перестановке строк решение системы не изменится. Перестановка столбцов k и h изменит решение: теперь позиция k вектора решения соответствует переменной , позиция h - переменной . При исключении в следующем столбце снова потребуется перестановка столбцов и т.д.

Чтобы фиксировать перестановки столбцов и затем восстановить естественный порядок следования неизвестных в векторе решения введем вспомогательный вектор Индекс вектора - номер позиции в векторе решений, значение компоненты - номер неизвестного, соответствующего этой позиции. Например, означает, что в позиции 5 указано значение неизвестного . Перед началом исключения (т.е. все "стоят на своих местах"). При перестановке столбцов матрицы переставляются и соответствующие компоненты вектора L, в нашем случае - компоненты и . Таким образом, вектор L отслеживает соответствие "позиция - номер неизвестного". Все другие действия, предусмотренные алгоритмом исключения, остаются неизменными: если , матрица вырождена; строку k делим на ; выполняем исключение в столбце k и т.д.

По окончании исключения полагаем:

- для метода Гаусса:



- для метода Жордана:

.

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

(2)

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

В памяти компьютера система представляется тремя векторами: - главная диагональ; - диагонали, параллельные главной; - вектор правых частей.

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

Более простым оказывается поиск коэффициентов, связывающих и . Положим

. (3)

Первое уравнение системы (2) определяет

,

сопоставив это выражение с выражением (3) при , получаем

. (4)

Выразим (выражение (3)) через и подставим в i-е уравнение системы (2)

,

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

.

Сопоставив последнее выражение с выражением (3), получаем

. (5)

Рекуррентные формулы (4) и (5) позволяют вычислить коэффициенты для .

Из (3) имеем

.

Подставив это выражение в последнее уравнение системы (2), получим

.

Из выражения (3) для получаем значения .

Рассмотренный метод решения системы (2) называется методом прогонки.

Метод квадратного корня. Метод применим только к системам уравнений с симметричной матрицей (на комплексной плоскости - с эрмитовой матрицей). Пусть требуется решить систему уравнений

(6)

и матрица системы А симметрична: .

Симметричная матрица А может быть представлена в виде произведения трех матриц

, (7)

где S - верхняя треугольная матрица (, если );

D - диагональная матрица с элементами ;

- транспонированная матрица .

Соотношение (7) для определяет равенства

.

Для получаем



для получаем



Представление матрицы А в виде (7) сводит решение системы (6) к решению трех систем с треугольными либо диагональными матрицами

.

Решение последних систем получается обратным ходом метода Гаусса:



Метод требует примерно вдвое меньше арифметических операций, чем метод Гаусса.

Определитель матрицы А вычисляется по формуле

.
З А Д А Н И Я
1. Составить программу решения m систем линейных алгебраических уравнений порядка n с общей матрицей

AX1 = B1, AX2 = B2, ..., AXm = Bm

методом Гаусса (Жордана) с выбором ведущего элемента по столбцам.

Входными параметрами программы являются: n - порядок системы; m - число систем и расширенная матрица A порядка n*(n+m), в первых n столбцах которой располагаются коэффициенты при неизвестных (матрица A), а в следующих m столбцах - правые части систем.

Выходным параметром программы является матрица X размером n*m, в столбцах которой располагаются m решений систем линейных уравнений.

Исходные данные вводятся из файла. В файл результатов записываются: исходная матрица системы; матрица решений X; контроль решения - матрица U=A*X и матрица правых частей B в виде

ui1, …, uim :: bi1, …, bim (i=1, …, n).
2. Составить программу решения m систем линейных алгебраических уравнений порядка n с общей матрицей

AX1 = B1, AX2 = B2, ..., AXm = Bm

методом Гаусса (Жордана) с выбором ведущего элемента по строкам.

Входными параметрами программы являются: n - порядок системы; m - число систем и расширенная матрица A порядка n*(n+m), в первых n столбцах которой располагаются коэффициенты при неизвестных (матрица A), а в следующих m столбцах - правые части систем.

Выходным параметром программы является матрица X размером n*m, в столбцах которой располагаются m решений систем линейных уравнений.

Исходные данные вводятся из файла. В файл результатов записываются: исходная матрица системы; матрица решений X; контроль решения - матрица U=A*X и матрица правых частей B в виде

ui1, …, uim :: bi1, …, bim (i=1, …, n).
3. Составить программу решения m систем линейных алгебраических уравнений порядка n с общей матрицей

AX1 = B1, AX2 = B2, ..., AXm = Bm

методом Гаусса (Жордана) с выбором ведущего элемента по всей матрице.

Входными параметрами программы являются: n - порядок системы; m - число систем и расширенная матрица A порядка n*(n+m), в первых n столбцах которой располагаются коэффициенты при неизвестных (матрица A), а в следующих m столбцах - правые части систем.

Выходным параметром программы является матрица X размером n*m, в столбцах которой располагаются m решений систем линейных уравнений.

Исходные данные вводятся из файла. В файл результатов записываются: исходная матрица системы; матрица решений X; контроль решения - матрица U=A*X и матрица правых частей B в виде

ui1, …, uim :: bi1, …, bim (i=1, …, n).

4. Составить программу вычисления обратной матрицы для матрицы произвольного порядка n методом Гаусса (Жордана) с выбором ведущего элемента по столбцам.

Порядок и коэффициенты исходной матрицы вводятся из файла. В файл результатов записываются: исходная матрица; обратная матрица; произведение исходной матрицы на обратную.

5. Составить программу вычисления обратной матрицы для матрицы произвольного порядка n методом Гаусса (Жордана) с выбором ведущего элемента по строкам.

Порядок и коэффициенты исходной матрицы вводятся из файла. В файл результатов записываются: исходная матрица; обратная матрица; произведение исходной матрицы на обратную.

6. Составить программу вычисления обратной матрицы для матрицы произвольного порядка n методом Гаусса (Жордана) с выбором ведущего элемента по всей матрице.

Порядок и коэффициенты исходной матрицы вводятся из файла. В файл результатов записываются: исходная матрица; обратная матрица; произведение исходной матрицы на обратную.

7. Составить программу вычисления определителя для матрицы произвольного порядка n методом Гаусса с выбором ведущего элемента по всей матрице.

Порядок и коэффициенты исходной матрицы вводятся из файла.
8. Для аппроксимации произвольной функции y = f(x) на некотором отрезке [a, b] с помощью интерполяционного многочлена степени n

Pn(x) = c0 + c1x + ... + cnxn

в n+1 точках xi[a, b], i = 0, ..., n вычисляют значения функции yi = f(xi), а затем решают систему n+1 линейных уравнений

yi = Pn(xi), i = 0, ..., n

относительно неизвестных коэффициентов ck. Написать программу, реализующую этот алгоритм.

Входными параметрами программы будут: внешняя функция f(x); концы отрезка a, b; n - число узлов интерполяции; а выходными параметрами - коэффициенты интерполяционного полинома ck, k = 0, ..., n. Провести численные эксперименты для функций y = e-x и y = sin10x на отрезке [0, 1].
9. Ищется зависимость величины y от величины x в виде полинома m-ой степени

y  Pm(x) = a0 + a1x + a2x2 + ... +amxm.

Для этой цели определяют экспериментально значения yi в n точках xi, i = 1, ..., n, где n>m. Коэффициенты полинома определяются из условия минимума среднеквадратичного отклонения



Приравняв к нулю частные производные функции S получаем систему из m+1 линейных уравнений относительно неизвестных коэффициентов a0, a1, ..., am



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

Вывести формулы для системы линейных уравнений, которым удовлетворяют коэффициенты ak, и составить программу, которая для заданных n экспериментальных точек xi, yi, i = 1, ..., n находит m+1 коэффициент ak, k = 0, ..., m аппроксимирующего полинома m-ой степени.

Провести численные эксперименты для функций y = e-x, y = sin10x на отрезке [0, 1].
10. Для численного определения коэффициентов характеристического многочлена матрицы A произвольного порядка n

det(A - E) = p0 + p1 +p22 + ... + pnn

использовать следующий прием: найти методом Гаусса n+1 значение определителя в n+1 точке 1, 2, ..., n+1, а затем решить систему из n+1 уравнений с n+1 неизвестными p0, p1, ..., pn методом Гаусса (см. задачу 8). Составить соответствующую программу, в которой входными параметрами являются матрица A и ее порядок n, а выходными - коэффициенты характеристического многочлена pi, i = 0, ..., n.

Порядок и коэффициенты исходной матрицы вводятся из файла.
11. Составить рекурсивную процедуру вычисления определителя матрицы методом разложения по строке (столбцу). Используя процедуру вычислить определитель заданной матрицы. Порядок и коэффициенты матрицы вводятся из файла.

12. Составить программу решения системы линейных уравнений методом Гаусса для трехдиагональной матрицы.

Порядок и коэффициенты матрицы (главная и соседние с ней диагонали), вектор правых частей вводятся из файла. В файл результатов выдаются: исходная система, решение системы, результат подстановки решения в систему в виде “левая часть = правая часть”.

13. Составить программу вычисления обратной матрицы методом Гаусса для трехдиагональной матрицы.

Порядок и коэффициенты матрицы (главная и соседние с ней диагонали) вводятся из файла. В файл результатов выдаются: исходная матрица, обратная матрица, произведение исходной матрицы на обратную.

14. Составить программу решения системы линейных уравнений методом Гаусса для пятидиагональной матрицы.

Порядок и коэффициенты матрицы (главная и соседние с ней диагонали), вектор правых частей вводятся из файла. В файл результатов выдаются: исходная система, решение системы, результат подстановки решения в систему в виде “левая часть = правая часть”.

15. Составить программу вычисления обратной матрицы методом Гаусса для пятидиагональной матрицы.

Порядок и коэффициенты матрицы (главная и соседние с ней диагонали) вводятся из файла. В файл результатов выдаются: исходная матрица, обратная матрица, произведение исходной матрицы на обратную.

16. Составить программу решения системы уравнений Ax = b для симметричной матрицы A методом квадратного корня.

Порядок и коэффициенты матрицы, вектор правых частей вводятся из файла. В файл результатов выдаются: исходная система, решение системы, результат подстановки решения в систему в виде “левая часть = правая часть”.

17. Составить программу вычисления определителя симметричной матрицы методом квадратного корня. Порядок и коэффициенты матрицы вводятся из файла.

18. Составить программу обращения симметричной матрицы методом квадратного корня.

Порядок и коэффициенты матрицы вводятся из файла. В файл результатов выдаются: исходная матрица, обратная матрица, произведение исходной матрицы на обратную.

19. Составить программу вычисления определителя пятидиагональной симметричной матрицы методом квадратного корня. Порядок и коэффициенты матрицы вводятся из файла.
20. Доказать, что для симметричной трехдиагональной теплицевой матрицы



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



где


и величины i определяются рекуррентными соотношениями:

1 = b1; i = a2/(bi - i-1), i = 2, ..., n-1.

Использовать это разложение для вычисления определителя матрицы A.

21. Для симметричной трехдиагональной теплицевой матрицы A использовать разложение, описанное в задаче 20, для решения системы уравнений Ax = b.

Порядок и коэффициенты матрицы, вектор правых частей вводятся из файла. В файл результатов выдаются: исходная система, решение системы, результат подстановки решения в систему в виде “левая часть = правая часть”.

22. Для симметричной трехдиагональной теплицевой матрицы A использовать разложение, описанное в задаче 20, для вычисления обратной матрицы.

Порядок и коэффициенты матрицы вводятся из файла. В файл результатов выдаются: исходная матрица, обратная матрица, произведение исходной матрицы на обратную.

23. Использовать разложение, описанное в задаче 20, для составления подпрограммы-функции, вычисляющей f() = det(A - E) для симметричной трехдиагональной теплицевой матрицы A. Найти все n корней уравнения f() = 0 с помощью пошагового разбиения отрезка a-2b    a+2b, где b = max(bi), i = 1, ..., n сначала на 1000 равных интервалов, затем - последовательного удвоения числа разбиений до тех пор, пока число интервалов, на концах которых знаки функции различны, не станет равным порядку матрицы A.

24. Составить программу решения системы уравнений Ax = b для трехдиагональной матрицы A методом прогонки.

Порядок и коэффициенты матрицы (главная и соседние с ней диагонали), вектор правых частей вводятся из файла. В файл результатов выдаются: исходная система, решение системы, результат подстановки решения в систему в виде “левая часть = правая часть”.

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

Порядок и коэффициенты матрицы (главная и соседние с ней диагонали) вводятся из файла. В файл результатов выдаются: исходная матрица, обратная матрица, произведение исходной матрицы на обратную.
26. Дана краевая задача для линейного дифференциального уравнения

y’’ + p(x)y’ + q(x)y = f(x); y(a) = ya; y(b) = yb.

Для численного решения задачи разбиваем отрезок интегрирования [a, b] на n равных интервалов, ищем решение в узлах xi = a+ih, i = 0, 1, ..., n, h=(b-a)/n. Для вычисления производных используем приближенные формулы



Краевая задача сводится к решению системы линейных уравнений с трехдиагональной матрицей


Составить программу, входными параметрами которой будут функции p(x), q(x), f(x), параметры a, b, n; а выходными - значения функции yi в узлах xi. Для решения системы линейных уравнений использовать метод прогонки.
27. Составить программу решения краевой задачи

y’’ = x + y; y(0) = 0; y(1) = 0,

разбив отрезок [0, 1] на 100 равных интервалов и сведя краевую задачу к решению системы линейных алгебраических уравнений методом прогонки.

Сравнить найденное решение с точным

y = sh(x)/sh(1) - x.
Л И Т Е Р А Т У Р А

1. Крячков А.В., Сухинина И.В., Томшин В.К. Программирование на С и С++, практикум. М.: Изд-во Радио и связь, 1997.

2. Касьянов В.Н., Сабельфельд В.К. Сборник заданий по практикуму на ЭВМ. М.: Наука, 1986.

3. Мак-Кракен. Численные методы и их программирование на

ФОРТРАНЕ.

4. Форсайт Дж., Молер К. Численное решение систем линейных

уравнений. М., МИР, 1969.

5. Воеводин В.В. Линейная алгебра. М., 1974.

6. Воеводин В.В. Вычислительные основы линейной алгебры. М.,

ФМЛ, 1977.

7. Форсайт Дж., Малькольм М., Моулер К. Машинные методы

математических вычислений. М., МИР, 1980.

8. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М., МЛ, 1984.




Похожие:

Решение систем линейных алгебраических уравнений прямые методы. Дана система линейных алгебраических уравнений. Требуется найти решение системы iconРешение системы линейных алгебраических уравнений
Цель: Освоить технологию решения систем линейных алгебраических уравнений в интегрированной среде MathCad
Решение систем линейных алгебраических уравнений прямые методы. Дана система линейных алгебраических уравнений. Требуется найти решение системы iconПрямые методы решения систем линейных алгебраических уравнений
Прямые методы решения систем линейных алгебраических уравнений. Лабораторная работа для студентов дневного отделения. Специальность:...
Решение систем линейных алгебраических уравнений прямые методы. Дана система линейных алгебраических уравнений. Требуется найти решение системы iconРешение систем линейных алгебраических уравнений. Схема единственного деления
Метод простых итераций для решения систем линейных алгебраических уравнений. Условия сходимости
Решение систем линейных алгебраических уравнений прямые методы. Дана система линейных алгебраических уравнений. Требуется найти решение системы icon2. системы линейных алгебраических уравнений
Система линейных алгебраических уравнений, содержащая уравнений и неизвестных имеет следующий вид
Решение систем линейных алгебраических уравнений прямые методы. Дана система линейных алгебраических уравнений. Требуется найти решение системы iconРешение систем линейных алгебраических уравнений и неравенств. Выпуклые многогранники и многогранные области
...
Решение систем линейных алгебраических уравнений прямые методы. Дана система линейных алгебраических уравнений. Требуется найти решение системы iconОтчет о выполнении задания по теме "Системы линейных алгебраических уравнений"
Написать программу на языке matlab, реализующую заданный метод решения систем линейных алгебраических уравнений. В качестве входных...
Решение систем линейных алгебраических уравнений прямые методы. Дана система линейных алгебраических уравнений. Требуется найти решение системы iconЛекция Исследование и решение систем алгебраических уравнений. Основные вопросы
При раскрытии понятий определителя и матрицы, при решении сис-тем линейных уравнений мы рассматривали в основном систему из n линей-ных...
Решение систем линейных алгебраических уравнений прямые методы. Дана система линейных алгебраических уравнений. Требуется найти решение системы iconРешение систем линейных уравнений. Система линейных алгебраических уравнений (слау) имеет вид: 1) или в матричной форме Ax = B
Слау обычно основаны на приведении матрицы в системе 2 к треугольному виду, т к системы с треугольными матрицами легко решаются путем...
Решение систем линейных алгебраических уравнений прямые методы. Дана система линейных алгебраических уравнений. Требуется найти решение системы iconРешение систем линейных алгебраических уравнений с ленточными матрицами. Пример решения линейной системы с трехдиагональной матрицей
Метод Гаусса для решения системы линейных алгебраических уравнений. Устойчивость метода Гаусса. Использование метода Гаусса для вычисление...
Решение систем линейных алгебраических уравнений прямые методы. Дана система линейных алгебраических уравнений. Требуется найти решение системы iconМетодические указания и задания к самостоятельной работе студентов по разделу «Методы решения систем линейных алгебраических уравнений»
Если матрица а неособенная, т е detА≠0, то система (1) имеет единственное решение
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org