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

Курсовая работа: «Решение систем n линейных уравнений с n неизвестными».

Обращаем Ваше внимание, что в соответствии с Федеральным законом N 273-ФЗ «Об образовании в Российской Федерации» в организациях, осуществляющих образовательную деятельность, организовывается обучение и воспитание обучающихся с ОВЗ как совместно с другими обучающимися, так и в отдельных классах или группах.

1. Решение систем n линейных уравнений с n неизвестными

1.1. Основные понятия

Системой m линейных уравнений с n неизвестными называется система уравнений вида (1):

Систему линейных уравнений (1) можно записать в матричной форме

Здесь A – матрица системы; X – матрица- столбец неизвестных; B – матрица-столбец свободных членов.

С системой линейных уравнений (1) связана ещё одна матрица ,

полученная из матриц A добавлением столбца B свободных членов, и называемая расширенной матрицей системы (1):

Если в системе линейных уравнений (1) все свободные члены равны нулю (т. е. B – нулевая матрица-столбец), то она называется однородной, в противном случае – неоднородной.

Решением системы линейных уравнение называется упорядоченная совокупность n чисел α1,α2,…,αn, которая при подстановке в систему обращает каждое уравнение в тождество.

Если система линейных уравнений имеет хотя бы одно решение, то она называется совместной, в противном случае – несовместной.

Две системы линейных уравнений называются равносильными (эквивалентными), если равны множества их решений.

1.2. Решение системы методом обратной матрицы

Пусть дана система n линейных уравнений с n неизвестными, у которой матрица A системы – невырожденная, т. е. | A |≠0. Запишем систему в матричной форме: AX=B .

Так как | A |≠0, то существует матрица А -1 . Умножим слева обе части матричного уравнения на А -1 : А -1 АХ = А -1 В или

Равенство (4) – матричная форма записи решения системы (1).

Для того чтобы найти элементы матрицы X неизвестных, нужно найти обратную матрицу А -1 и умножить её на столбец свободных членов B .

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

Запишем систему в матричном виде:

Выясним, является ли матрица A системы невырожденной:

Следовательно, матрица A является невырожденной. Поэтому существует обратная матрица А -1 ; воспользуемся формулой:

Найдём произведение А -1 В :

Матрица неизвестных равна:

Ответ можно записать также в виде .

1.3. Решение системы методом Крамера

Система n линейных уравнений с n неизвестными называется крамеровской, если матрица A системы является невырожденной (т. е. | A |≠0).

Теорема (Крамера). Крамеровская система n линейных уравнений с n неизвестными имеет единственное решение, которое находится по формулам (5) :

где | A | − определитель матрицы системы, | Aij | − определитель матрицы, получаемый из матрицы A заменой j -го столбца столбцом свободных членов B .

Заметим, что способ решения системы линейных уравнений, основанный на формулах Крамера, называют методом или правилом Крамера.

Решить систему методом Крамера.

Данная система линейных уравнений является крамеровской (так как | A |≠0). Согласно формулам (5) имеем:

Замечание. Метод обратной матрицы и метод Крамера решения систем линейных уравнений становятся трудоёмкими при n ≥4.

1.4. Решение системы уравнений методом Гаусса

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

Эквивалентными (равносильными) преобразованиями системы линейных уравнений называются следующие действия:

1) перестановка местами двух уравнений системы,

2) умножение любого уравнения на число, отличное от нуля,

3) прибавление к одному из уравнений другого уравнения, умноженного на любое число,

4) удаление (вписывание) уравнения вида 0 x 1+0 x 2+…+0 xn =0.

На практике проделывают эквивалентные преобразования не над системой, а над её расширенной матрицей.

Проиллюстрируем применение метода Гаусса.

Методом Гаусса решить систему уравнений:

Выпишем расширенную матрицу и с помощью эквивалентных преобразований приведем её к ступенчатому виду:

1-ю строку прибавим к 3-й, а затем умножим её на (−1) и прибавим к 4-й.

В дальнейшем 1-ю строку не трогаем, работаем со 2-й строкой.

Прибавим 2-ю строку к 3-й, а затем прибавим утроенную 2-ю строку к 4-й. Далее первые две строки не трогаем, работаем с 3-й.

Умножим 3-ю строку на 7 и прибавим к 4-й .

Таким образом, в результате проведённых преобразовании пришли к следующей системе линейных уравнений, равносильной данной:

Курсовая работа на тему: Решение систем линейных уравнений. Метод Гаусса

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕСИОНАЛЬНОГО ОБРАЗОВАНИЯ

«РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ им А. И.ГЕРЦЕНА»

Кафедра информационных и коммуникационных технологий

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

студентка 2 курса 1 гр

кандидат педагогических наук, доцент

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

1) вывод рекуррентной формулы

3) код программы

4) контрольный пример

Введение

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

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

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

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

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

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

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

Итак, перед нами система n линейных алгебраических уравнений с n неизвестными:

(1.1)

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

А — матрица, X – вектор-столбец неизвестных, B- вектор-столбец свободных членов.

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

o Метод определителей (метод Крамера) хорошо известный из курса алгебры;

o Матричное решение: X=A-1B (если известна обратная матрица);

o Различные варианты метода исключения неизвестных (метода Гаусса).

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

Практическое применение первых двух методов может оказаться неэффективным или вообще невозможным. Если попробовать решать «в лоб» систему 15 линейных уравнений с 15 неизвестными с помощью формулы Крамера, то придется вычислить 16 определителей порядка 15, что приведет к выполнению примерно 2*16*15!*14 умножений и сложений. Для выполнения этих вычислений на ЭВМ с быстродействием 106 арифметических операций в секунду потребуется почти 10 недель непрерывной работы. С практической точки зрения при достаточно больших размерах системы матричное решение также является малопривлекательным, поскольку задача нахождения обратной матрицы сама по себе не проще задачи решения системы.

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

o Метод простой итерации;

o Метод Зейделя.

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

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

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

2. Постановка задачи:

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

2.1. Вывод рекуррентной формулы

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

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

Решение этой задачи сводится сводиться к двум этапам.

1 этап. Прямой ход.

Матрица А преобразуется в эквивалентную ей левую верхнюю треугольную матрицу, таким же преобразованиям подвергается и вектор-столбец свободных членов В, который обычно присоединяется к матрице А справа как n+1 столбец, но я присоединю его слева как 1 столбец для того, чтобы удобнее было вычислять неизвестные данной нам матрицы.

2 этап. Обратный ход.

На этом ходе находятся корни уравнений методом обратной подстановки.

Алгоритм действия на 1 этапе.

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

Для этого необходимо:

1. преобразование матрицы А начнем из верхнего правого угла, где расположен элемент а1n+1 и будем двигаться сверху вниз и справа налево

2. двигаясь сверху вниз под диагональю в каждом (n-i+1)-том столбце будем получать нули

3. двигаясь справа налево включая столбец свободных членов обеспечивает эквивалентное преобразование элементов начиная с (n+1) столбца.

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

1.Для получения нуля на месте ведомого элемента ak(n-i+1) необходимо получить новый коэффициент преобразования для k-той строки. Он равен:

(2.1)

2.Далее в каждом цикле частичного обнуления (n-i+1)-го столбца из каждой ведомой k-той строки вычитается ведущая строка кратная коэффициенту преобразования , с точки зрения математики это описывается следующим образом:

(2.2)

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

Алгоритм действий на этапе обратного хода.

В результате преобразования имеем:

Обобщенные формулы для нахождения корней систем линейных уравнений имеет следующий вид:

(2.3)

(2.4)

Dim x(3), p, p5, S As Decimal

Dim i, k, n, j, i1, j1, t, m, m5, l, m1, max As Integer

Dim strSt As String

Console. WriteLine(«Метод оптимального исключения по столбцам «)

Console. WriteLine(«с выбором главного элемента по строкам»)

‘вывод матрицы на экран

Console. WriteLine(«Исходная матрица»)

For i = 0 To n — 1

strSt = FormatNumber(mas(i, j), 2)

Console. Write(» <0>«, strSt)

‘выбор главного элемента по строкам

For i = 0 To n — 1

max = Math. Abs(mas(i, n — i))

For j = n — i To 1 Step -1

m5 = Math. Abs(mas(i, j))

If m5 > max Then

If j1 = n — i Then

‘конец алгоритма выбора главного элемента

For l = 0 To n — 1

mas(l, n — i) = mas(l, j1)

Console. WriteLine(«Преобразованная матрица»)

For t = 0 To n — 1

strSt = FormatNumber(mas(t, j), 2)

Console. Write(» <0>«, strSt)

Console. WriteLine(«Преобразовываем матрицу в треугольную левую верхнюю»)

‘процедура прямого хода

‘преобразовываем матрицу в левую верхнюю треугольную

For i = 0 To n — 2

For k = i + 1 To n — 1

p = mas(k, n — i) / mas(i, n — i)

For j = n — i To 0 Step -1

mas(k, j) = mas(k, j) — p * mas(i, j)

‘вывод преобразованной матрицы

For t = 0 To n — 1

strSt = FormatNumber(mas(t, j), 2)

Console. Write(» <0>«, strSt)

‘вывод полученной матрицы

Console. WriteLine(«Полученная матрица»)

For i = 0 To n — 1

strSt = FormatNumber(mas(i, j), 2)

Console. Write(» <0>«, strSt)

‘процедура обратного кода

x(0) = mas(n — 1, 0) / mas(n — 1, 1)

For j = 0 To n — i — 2

S = S + mas(i, j + 1) * x(j)

x(n — i — 1) = (mas(i, 0) — S) / mas(i, n — i)

Loop While i >= 0

Console. WriteLine(«Полученные значения х»)

For i = 0 To n — 1

Console. Write(«x<0>=», i + 1)

strSt = FormatNumber(x(i), 2)

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

1. Получим новый коэффициент преобразования для каждой k-ой строки.

2. Для обнуления 5-го столбца из каждой ведомой k-той строки вычитается ведущая строка кратная коэффициенту преобразования .

3. Получим новый коэффициент преобразования для каждой k-ой строки.

4. Для обнуления 4-го столбца из каждой ведомой k-той строки вычитается ведущая строка кратная коэффициенту преобразования .

5. Получим новый коэффициент преобразования для каждой k-ой строки.

6. Для обнуления 3-го столбца из каждой ведомой k-той строки вычитается ведущая строка кратная коэффициенту преобразования .

7. Вычислим переменные х:

Сравним полученные результаты с результатом программы

Метод оптимального исключения по столбцам

с выбором главного элемента по строкам

17,00 5,00 2,00 4,00 6,00

13,00 4,00 3,00 1,00 5,00

22,00 6,00 5,00 3,00 8,00

20,00 3,00 10,00 5,00 2,00

17,00 4,00 2,00 5,00 6,00

13,00 1,00 3,00 4,00 5,00

22,00 3,00 5,00 6,00 8,00

20,00 5,00 10,00 3,00 2,00

Преобразовываем матрицу в треугольную левую верхнюю

17,00 4,00 2,00 5,00 6,00

-1,17 -2,33 1,33 -0,17 0,00

-0,67 -2,33 2,33 -0,67 0,00

14,33 3,67 9,33 1,33 0,00

17,00 4,00 2,00 5,00 6,00

-1,17 -2,33 1,33 -0,17 0,00

4,00 7,00 -3,00 0,00 0,00

5,00 -15,00 20,00 0,00 0,00

17,00 4,00 2,00 5,00 6,00

-1,17 -2,33 1,33 -0,17 0,00

4,00 7,00 -3,00 0,00 0,00

31,67 31,67 0,00 0,00 0,00

17,00 4,00 2,00 5,00 6,00

-1,17 -2,33 1,33 -0,17 0,00

4,00 7,00 -3,00 0,00 0,00

31,67 31,67 0,00 0,00 0,00

Полученные значения х

. Теория матриц (издание третье)./. Москва: „Наука”, главная редакция физико-математической литературы, 1967г. Математический энциклопедический словарь. Москва: „Советская энциклопедия”, 1988г. Интернет-ресурсы (*****) Выводила рекуррентные формулы студентка 2 курса института информационных технологий

Курсовая работа: Численные методы решения систем линейных уравнений

по информатике на тему:

«Численные методы решения

систем линейных уравнений»

студент 06–ИСТ, Фадеева Т.В.

2. Численные методы . 6

1) Матричный метод. 6

2) Метод Крамера. 9

3) Метод Гаусса …………. 12

4) Итерации для линейных систем….…..…..17

a) Итерация Якоби..………………. …..18

b) Итерация Гаусса – Зейделя..……. …20

1) Матричный метод. 22

2) Метод Крамера. 24

3) Метод Гаусса……. 26

4) Листинг программы.……………………….28

Польза введения расчётов. ……………………………….65

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

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

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

Любой численный метод линейной алгебры можно рассматривать как некоторую последовательность выполнения арифметических операций над элементами входных данных. Если при любых входных данных численный метод позволяет найти решение задачи за конечное число арифметических операций, то такой метод называется прямым . В противоположном случае численный метод называется итерационным . Прямые методы — это такие, как метод Гаусса, метод окаймления, метод пополнения, метод сопряжённых градиентов и др. Итерационные методы – это метод простой итерации, метод вращений, метод переменных направлений, метод релаксации и др. Здесь будут рассматриваться матричный метод, метод Гаусса и метод Крамера.

В данной работе будут рассмотрены численные методы в электронных таблицах Excel и программе MathCAD, MicrosoftVisualBasic.

Программа MathCAD по своему назначению позволяет моделировать в электронном документе научно–технические, а также экономические расчёты в форме, достаточно близкой к общепринятым ручным расчётам. Это упрощает составление программы расчёта, автоматизирует перерасчёт и построение графических иллюстраций подобно электронным таблицам Excel, документирование результатов как в текстовом редакторе Word.

Программа Mathcad известна за лёгкость, с которой математические уравнения, текст, и графика могут быть объединены в одном документе. Кроме того, вычислительные способности Mathcad распространяются от сложения столбца чисел к решению интегралов и производных, решение систем уравнений и больше.

Достоинством MathCAD является также наличие в его составе электронных книг. Одна из них – учебник по самой программе, другие – справочник по различным разделам математики, физики, радиоэлектроники и др.

Microsoft Office Excel . Если же говорить о программе Excel, которая является одной из наиболее известных в обработке электронных таблиц, то без преувеличения можно утверждать, что ее возможности практически неисчерпаемы.Обработка текста, управление базами данных — программа настолько мощна, что во многих случаях превосходит специализированные программы — редакторы или программы баз данных. Такое многообразие функций может поначалу запутать, нежели заставить применять их на практике. Но по мере приобретения опыта начинаешь по достоинству ценить то, что границ возможностей Excel тяжело достичь.За всю историю табличных расчетов с применением персональных компьютеров требования пользователей к подобным программам существенно изменились. В начале основной акцент в такой программе, как, например, Visi Calc , ставился на счетные функции. Сегодня, положение другое. Наряду с инженерными и бухгалтерскими расчетами организация и графическое изображение данных приобретают все возрастающее значение. Кроме того, многообразие функций, предлагаемое такой расчетной и графической программой, не должно осложнять работу пользователя. Программы для Windows создают для этого идеальные предпосылки.В последнее время многие как раз перешли на использование Windows в качестве своей пользовательской среды. Как следствие, многие фирмы, создающие программное обеспечение, начали предлагать большое количество программ для Windows.Visual Basic . MicrosoftVisualBasic – это мощная система программирования, позволяющая быстро и эффективно создавать приложения для MicrosoftWindows. В отличие от Excel и MathCADэто наиболее удобная программа для решения систем линейных уравнений. Простой пользовательский интерфейс, позволяющий легко переключаться с проекта формы на сам код программы.

Удобное окно для кода самой программы:

Разрешимость системы линейных уравнений.

Когда мы говорим о главной матрице системы линейных уравнений, то всегда имеем в виду квадратную матрицу nЧn, т. е. матрицу с одинаковым количеством строк и столбцов. Это важно.

Если, например, количество строк (количество уравнений в системе) будет меньше, чем количество столбцов (фактически, количества неизвестных), то система будет неопределенной, т. е. мы не сможем однозначно определить все неизвестные (решить систему).

Но это не единственное ограничение. Из векторной алгебры известно, что система линейных уравнений имеет решение (однозначное) тогда и только тогда, когда ее главный определитель не равен нулю: Δ ≠ 0.

Рассмотрим случай, когда определитель системы равен нулю. Здесь возможны два варианта:

1. Δ = 0 и каждый из дополнительных определителей Δx_i = 0. Это имеет место только тогда, когда коэффициенты при неизвестных x_i пропорциональны, т. е. каждое уравнение системы получается из первого уравнения умножением обеих его частей на число k. При этом система имеет бесчисленное множество решений.

2. Δ = 0 и хотя бы один дополнительный определитель Δx_i ≠ 0. Это имеет место только тогда, когда коэффициенты при всех неизвестных x_i , пропорциональны. При этом получается система из противоречивых уравнений, которая не имеет решений.

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

Пусть дана система линейных уравнений:

Рассмотрим матрицу, составленную из коэффициентов при неизвестных:

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

Тогда, используя правило умножение матриц, эту систему уравнений можно записать так:

Равенство (1) называется матричным уравнением или системой уравнений в матричном виде.

Матрица А коэффициентов при неизвестных называется главной матрицей системы.

Иногда рассматривают также расширенную матрицу системы, т. е. главную матрицу системы, дополненную столбцом свободных членов, которую записывают в следующем виде:

Любую линейную систему уравнений можно записать в матричном виде. Например, пусть дана система:

Эта система из двух уравнений с тремя неизвестными – x, y,. В высшей математике можно рассматривать системы из очень большого числа уравнений с большим количеством неизвестных и поэтому неизвестные принято обозначать только буквой х, но с индексами:

Запишем эту систему в матричном виде:

Здесь главная матрица системы:

Расширенная матрица будет иметь вид:

Решения матричных уравнений.

Матричные уравнения решаются при помощи обратных матриц. Уравнение решается следующим образом. Пусть матрица А – невырожденная (D ≠ 0), тогда существует обратная матрица А-1. Умножив на нее обе части матричного уравнения, имеем А-1(АХ) = А-1В. Используя сочетательный закон умножения, перепишем это равенство в виде

Поскольку А-1 А = Е и ЕХ = Х, находим:

Таким образом, чтобы решить матричное уравнение, нужно:

1. Найти обратную матрицу А-1.

2. Найти произведение обратной матрицы А-1 на матрицу столбец свободных членов В, т. е А-1В.

Пользуясь определением равных матриц, записать ответ.

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

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

При решении систем линейных уравнений по методу Крамера последовательно выполняется следующий алгоритм:

1. Записывают систему в матричном виде (если это еще не сделано).

2. Вычисляют главный определитель системы:

3. Вычисляют все дополнительные определители системы:

4. Если главный определитель системы не равен нулю, то выполняют пункт 5. Иначе рассматривают вопрос о разрешимости данной системы (имеет бесчисленное множество решений или не имеет решений). Находят значения всех неизвестных по формулам Крамера для решения системы n линейных уравнений с n неизвестными, которые имеют вид:

Решить по методу Крамера систему из трех уравнений с тремя неизвестными:

Запишем главный и побочные определители системы:

Вычислим эти определители:

Δ1 = -112+(-45)+(-192)-(-240)-24-168 = -112-45-192+240-24-168 = 240-541 = -301.

Δ2 = -36-420-280-75+196-288 = 196-1099 = -903.

Δ3 = -144-147-30-140+27-168 = -629+27 = -602.

Главный определитель системы не равен нулю. Находим неизвестные по формулам Крамера.

Подставим найденные значения определителей в формулы Крамера:

x1 = Δ1/Δ = -301/(-205) = 1,468292682927 ≈ 1,47;

x2 = Δ2/Δ = -903/(-205) = 4,40487804878 ≈ 4,4;

x3 = Δ3/Δ = -602/(-205) = 2,936585365854 ≈ 2,93.

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

Напомним, что главным определителем системы называется определитель главной матрицы системы, составленной из коэффициентов при неизвестных:

Если в главном определителе системы заменить поочередно столбцы коэффициентов при x₁ , x₂ . x_n на столбец свободных членов, то получим n дополнительных определителей (для каждого из n неизвестных):

При этом важен вопрос о разрешимости данной системы, который решается сравнением главного и дополнительных определителей системы с нулем:

Метод Гаусса – прямой и обратный ход.

Рассмотрим метод Гаусса. Например, пусть дана расширенная матрица некоторой системы m линейных уравнений c n неизвестными:

Будем считать, что a₁₁ ≠ 0 (если это не так, то достаточно переставить первую и некоторую другую строку расширенной матрицы местами). Проведем следующие элементарные преобразования:

Т. е. от каждой строки расширенной матрицы (кроме первой) отнимаем первую строку, умноженную на частное от деления первого элемента этой строки на диагональный элемент а₁₁ .

В результате получим матрицу:

Т. е. первая строка осталась без изменений, а в столбце под а₁ 1 на всех местах оказались нули. Обратим внимание, что преобразования коснулись всех элементов строк, начиная со второй, всей расширенной матрицы системы.

Теперь наша задача состоит в том, чтобы получить нули подо всеми диагональными элементами матрицы А – a_ij , где I = j.

Повторим наши элементарные преобразования, но уже для элемента α₂₂ .

Т. е. от каждой строки расширенной матрицы (теперь кроме первой и второй) отнимаем вторую строку, умноженную на частное от деления первого элемента этой (текущей) строки на диагональный элемент α₂₂ .

Такие преобразования продолжаются до тех пор, пока матрица не приведется к верхнее — треугольному виду. Т. е. под главной диагональю не окажутся все нули:

Вспомнив, что каждая строка представляет собой одно из уравнений линейной системы уравнений, легко заметить, что последнее m-ое уравнение принимает вид:

Отсюда легко можно найти значение первого корня – x_n = δ_m /γ_mn .

Подставив это значение в предыдущее m-1-е уравнение, легко получим значение x_n-1 -ого корня.

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

Рассмотрим систему уравнений:

Главный определитель данной системы:

Т. е. система определена и разрешима. Решим ее по методу Гаусса.

Проведем прямой ход метода Гаусса, выписав предварительно расширенную матрицу системы:

Получим нули под главной диагональю в первом столбце расширенной матрицы. Для получения нуля в элементе a21 (т. е. под диагональю во второй строке матрицы) вторую строку матрицы преобразуем по формуле C₂ -(a₂₁ /a₁₁ )*C₁ = C₂ -(2/1)*C₁ = C₂ -2*C₁ :

Аналогично поступаем и с элементом а31 (т. е. под диагональю в третьей строке матрицы). Третью строку матрицы преобразуем по формуле C₃ -(a₃₁ /a₁₁ )*C₁ = C₃ -(-1/1)*C₁ = C₃ +C₁ :

Таким образом, мы получили нули под главной диагональю в первом столбце расширенной матрицы. Осталось получить нуль под главной диагональю во втором столбце матрицы, т. е. на месте элемента а32. Для этого третью строку матрицы преобразуем по формуле C₃ -(a₃₂ /a₂₂ )*C₂ = C₃ -(1/-2)*C₂ = C₃ +1/2C₂ :

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

Эта матрица эквивалентна системе:

Обратным ходом метода Гаусса найдем корни системы. Из последнего уравнения найдем корень х₃ :

Корень x₃ = -3/5 найден. Подставим его в верхнее (второе) уравнение системы (-2x₂ -3x₃ = 1):

Корень x₂ = 2/5 найден. Подставим его и корень х₃ в верхнее (первое) уравнение системы (x₁ -x₂ +x₃ = 0):

Итак, метод Гаусса (или, иначе, метод последовательного исключения неизвестных) состоит в следующем:

1. Путем элементарных преобразований систему уравнений приводят к эквивалентной ей системе с верхне-треугольной матрицей. Эти действия называют прямым ходом.

2. Из полученной треугольной системы переменные находят с помощью последовательных подстановок (обратный ход).

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

Итерация для линейных систем.

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

Для определенности ограничимся системой из четырех уравнений с четырьмя неизвестными (система четвертого порядка), которую запишем в виде:

Разрешим первое уравнение системы относительно х₁ :

Затем разрешим второе уравнение относительно х₂ и т. д. Тогда систему можно переписать в виде:

гдеα = -a_ik /a_ii , i = 1, 2, 3, 4; k = 1, 2, 3, 4, 5.

Система является частным случаем записи вида:

При этом линейная функция L₁ фактически не зависит от х₁ .

Зададим какие-либо начальные значения неизвестных (нулевые приближения):

Подставляя эти значения в правые части системы (*), получим первые приближения:

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

Условия сходимости итерационного процесса.

Установим условия, выполнение которых обеспечит сходимость получающихся приближений к истинному (точному) решению системы х₁ , х₂ , х₃ , х₄ .

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

Это условие можно сформулировать и более точно:

Для сходимости процесса итераций достаточно, чтобы в каждом столбце сумма отношений коэффициентов системы к диагональным элементам, взятым из той же строки, была строго меньше единицы :

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

Уравнения можно записать в виде:

Это позволяет предложить следующий итерационный процесс:

или (другой вид записи)

Покажем, что если начать с точки P₀ = (х₁ (0) , х₂ (0) , х₃ (0) , х₄ (0) ) = (1, 2, 2), то итерация (3) сходится к решению (2, 4, 3). Подставим х₁ = 1, х₂ = 2, х₂ = 2 в правую часть каждого уравнения из (3), чтобы получить новые значения:

Новая точка P₁ = (х₁ (1) , х₂ (1) , х3 (1) , х₄ (1) ) = (1.75, 3.375, 3), ближе, чем P₀ .

Итерация, использующая (3), генерирует последовательность точекk >, которая сходится к решению (2, 4, 3):

Этот процесс называется итерацией Якоби и может использоваться для решения определенных типов линейных систем.

Процесс итерации Якоби иногда можно модифицировать для ускорения сходимости.

Отметим, что итеративный процесс Якоби производит три последовательности – <х₁ (k) >, <х₂ (k) >, <х₃ (k) >, <х₄ (k) >. Кажется разумным, что х₁ (k+1) может быть использовано вместо х₂ (k ). Аналогично х₁ (k+1) и х₂ (k+1) можно использовать в вычислении х₃ (k+1) . Например, для уравнений из системы (1) это даст следующий вид итерационного процесса Гаусса-Зейделя, использующий (3*):

Такой итерационный процесс даст результаты:

Т. е. к точному решению мы пришли уже на 10-ом шаге итерации, а не на 19, как в итерации Якоби.

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

Эти формулы как раз и задают собственно итерационный процесс.

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

Это условие можно сформулировать и более точно:

Для сходимости процесса итераций достаточно, чтобы в каждом столбце сумма отношений коэффициентов системы к диагональным элементам, взятым из той же строки, была строго меньше единицы:

3. Следует так же сказать, что итерационный процесс может проводиться как в виде итерации Якоби, так и в виде итерации Гаусса-Зейделя. В последнем случае сходимость итерационного процесса может существенно улучшиться.

1) Метод обратной матрицы.

2) Метод Крамера.

4) Листинг программы (Метод Крамера, Метод Гаусса, Метод обратной матрицы).

BorderStyle = 1 ‘Единственный Фиксированный

Caption = «Решение систем линейных уравнений»