Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Содержание

• 1. Точные методы решения систем линейных алгебраических уравнений
• 2. Прямые методы решения систем линейных алгебраических уравнений
• 2.1 Метод Крамера
• 2.2 Метод обратной матрицы
• 3. Реализация решения СЛАУ с помощью Microsoft Excel
• 4. Итерационные методы решения систем линейных алгебраических уравнений
• 4.1 Метод простой итерации
• 4.2 Метод простой итерации приближенного решения систем линейных алгебраических уравнений
• 4.3 Решение системы методом Крамера
• 4.4 Решение системы методом обратной матрицы
• 4.5 Решение системы методом простой итерации
• 5. Блок-схема алгоритма
• 6. Описание алгоритма
• 7. Программа на языке VBA
• 8. Результаты выполнения программы с заданной точностью
• Заключение
• Литература


Введение

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

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

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



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

Система линейных алгебраических уравнений с вещественными коэффициентами имеет вид:

a₁₁x₁+a₁₂x₂+a₁₃x₃+…+a_1nx_n=b₁

a₂₁x₁+a₂₂x₂+a₂₃x₃+…+a_2nx_n=b₂

a₃₁x₁+a₃₂x₂+a₃₃x₃+…+a_3nx_n=b₃

…………………………………………….

a_n1x₁+a_n2x₂+a_n3x₃+…+a_nnx_n=b_n

В матричной форме записи эта система принимает вид:

Ax=b, где

А - матрица системы, b - вектор правых частей, х - вектор неизвестных.

Необходимым и достаточным условием существования единственного решения систем линейных алгебраических уравнений является условие det A?0, т.е. определитель матрицы A не равен нулю. В случае равенства нулю определителя матрица A либо не имеет решения, либо имеет их бесчисленное множество.

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



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

2.1 Метод Крамера

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

Если определитель матрицы системы не равен нулю, то система имеет единственное решение, которое находится по формуле Крамера:

где ?i - определитель матрицы, полученной из основной матрицы А заменой i-го столбца на столбец свободных членов системы, а ? - определитель основной матрицы. Эта формула называется формулой Крамера.

Определители _х1, _х2, … , _хn получаются путём замены коэффициентов при соответствующих неизвестных свободными членами.

x1= x2 = xn=

2.2 Метод обратной матрицы

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

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

Эту систему можно записать в виде матричного уравнения A * X = B,

Из полученного матричного уравнения необходимо выразить Х. Для этого умножим обе части матричного уравнения слева на А^-1, получим:

А^-1 * А * В = А^-1 * Х

Далее находится обратная матрица А^-1 и умножается на столбец свободных членов В.



3. Реализация решения СЛАУ с помощью Microsoft Excel

Значительно проще можно получить решение системы с помощью некоторых встроенных функций, имеющихся в Excel:

· МОПРЕД -- функция вычисления определителя квадратной матрицы;

· МОБР -- функция вычисления обратной матрицы;

· МУМНОЖ -- функция вычисления произведения двух матриц.

Для получения на экране решения системы выбирается ячейка, с которой начинается ответ. Получаем первое значение. Чтобы был виден весь ответ необходимо: выделить те ячейки, в которых должен появиться результат и нажать F2 одновременно с сочетанием клавиш Ctrl+Shift+Enter.



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

Помимо прямых методов решения систем линейных алгебраических уравнений существуют и приближенные методы решения СЛАУ. К ним относится метод простой итерации (метод Якоби) и метод Зейделя. Я выбрала метод простой итерации, так как он легко программируется.

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

Для того чтобы применить метод простой итерации к решению системы линейных алгебраических уравнений Ax=b с квадратной невырожденной матрицей А, необходимо предварительно преобразовать эту систему к виду: x=Bx+c.

Здесь В - квадратная матрица с элементами b_ij (i, j=1, 2, …, m), c - вектор-столбец с элементами с_i (i=1, 2, …, m).

В развернутой форме записи система имеет следующий вид:

x₁=b₁₁x₁+ b₁₂x₂ + b₁₃x₃ +…+ b_1mx_m +c₁

x₂=b₂₁x₁+ b₂₂x₂ + b₂₃x₃ +…+ b_2mx_m +c₂

……………………………………………………….

x_m=b_m1x₁+ b_m2x₂ + b_m3x₃ +…+ b_mmx_m +c_m

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

x₁=1/a₁₁(b₁-a₁₂x₂-a₁₃x₃-…-a_1mx_m),

из второго уравнения - неизвестное х₂:

x₂=1/a₂₂(b₂-a₂₂x₂-a₂₃x₃-…-a_2mx_m)

и т.д.

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

x₁=b₁₂x₂+ b₁₃x₃ +…+ b_1,1-mx_m-1 + b_1mx_m +c₁

x₂=b₂₁x₁+ b₂₃x₃ +…+ b_2,1-mx_m-1 + b_2mx_m +c₂

……………………………………………………….

x_m=b_m1x₁+ b_m2x₂ +...+ b_m,m-1x_m-1 +c_m ,

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

Выберем начальное приближение. Подставляя его в правую часть x=Bx+с и вычисляя полученное выражение, находим первое приближение: x⁽⁰⁾=(x₁⁽⁰⁾, x₂⁽⁰⁾, …, x_m⁽⁰⁾)

Продолжая этот процесс далее, получим последовательность приближений, вычисляемых по формуле: x⁽¹⁾=Bx⁽⁰⁾+c

Сходимость метода простой итерации.

Теорема. Пусть выполнено условие q<1.

Тогда:

· Решение системы x=Bx+c существует и единственное

· При произвольном начальном приближении х⁽⁰⁾ метод простой итерации сходится и справедлива оценка погрешность: ||x⁽ⁿ⁾- ||<=q⁽ⁿ⁾||x⁽⁰⁾- ||.

4.2 Метод простой итерации приближенного решения систем линейных алгебраических уравнений

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

Суть: Дана система уравнений, коэффициенты при неизвестных и свободные члены которой являются точными числами. Найти ее приближенное решение с точностью до е=0,0005.

Система:

0,91х₁-0,04х₂+0,21х₃-0,18х₄=-1,24

0,25х₁-1,23х₂-0,23х₃-0,09х₄=-1,04

-0,21х₁-0,23х₂+0,8х₃-0,13х₄=2,56

0,15х₁-0,31х₂+0,06х₃-1,04х₄=0,91

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

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

3. Составить программу с выводом на каждом шаге значений: х₁, х₂ , х_3, х₄ - координаты векторов-приближений, Е_к - абсолютные погрешности этих векторов.

4. Найти приближенное решение системы и выписать его координаты с верными значащими цифрами.

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

На рисунках рис.1 и рис.1.0 представлены матрица системы и матрица свободных членов этой системы соответственно.

Рис.1 Рис.1.0

1. Заменим первый столбик матрицы свободными членами и найдем определитель матрицы с помощью функции МОПРЕД. Результат показан на рис.1.1.

Рис.1.1

2. Заменим второй столбик матрицы свободными членами и найдем определитель матрицы. Результат показан на рис.1.2.

Рис.1.2

3. Заменим третий столбик матрицы свободными членами и найдем определитель матрицы. Результат показан на рис.1.3.

Рис.1.3

4. Заменим четвертый столбик матрицы свободными членами и найдем определитель матрицы. Результат показан на рис.1.4.

Рис.1.4



5. По формуле получаем решение системы, которое показано на рис.1.5.

Рис.1.5

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

На рисунках рис.2 и рис.2.0 представлены матрица системы и матрица свободных членов этой системы соответственно.

Рис.2 Рис.2.0

1. С помощью функции МОБР находим обратную матрицу данной. Результат показан на рис.2.1.

Рис.2.1

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

2. Умножаем полученную матрицу на свободные члены с помощью функции МУМНОЖ и получаем решение системы (рис.2.2).



Рис.2.2

4.5 Решение системы методом простой итерации

х₁ =1/0,91*(0,04х₂-0,21х₃+0,18х₄-1,24)

х₂ =-1/1,23*(-0,25х₁-0,23х₃+0,09х₄-1,04)

х₃ =1/0,8*(0,21х₁+0,23х₂+0,13х₄+2,56)

х₄ =-1/1,04*(-0,15х₁+0,31х₂-0,06х₃+0,91)

х₁ =0,04х₂-0,23х₃+0,19х₄-1,36

х₂ =0,2х₁-0,19х₃-0,07х₄+0,85

х₃ =0,26х₁+0,29х₂+0,16х₄+3,2

х₄ =0,14х₁-0,29х₂+0,06х₃-0,88

Начальное приближение: х⁰={-1.36; 0.85; 3.2; -0.88}

Подставляем начальное приближение в правую часть x=Bx+с и вычисляем полученное выражение, находим первое приближение: x⁽¹⁾={-2.2292; 0.0316; 2.9512; -1.1249}

Достаточное условие сходимости итерационной последовательности:

q=max<1

В данном случае q=0.7 -> 0.7<1 -> матрица удовлетворяет условию сходимости.



5. Блок-схема алгоритма



6. Описание алгоритма

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

2. Для этого из первого уравнения системы выразили х₁, из второго - х₂, из третьего - х₃ и из четвертого - х₄.

3. Свободные члены - это начальное приближение. В нашем случае это х⁰={-1.36; 0.85; 3.2; -0.88}

4. Мы подставили его в правую часть системы, приведенного вида, и получили первое приближение: x⁽¹⁾={-2.2277; 0.0529; 2.9424; -1.112}

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

6. Итерационный процесс прекращается, если выполняется неравенство:

maxⁿ_i=1|x^k_i- x^k-1_i|<=e*(1-q)/q, где е=0,0005 и q=0,7.



7. Программа на языке VBA

Реализация программы на языке VBA показана на рисунках рис.3а и продолжение на рис.3б.

Рис. 3а

Рис.3б



8. Результаты выполнения программы с заданной точностью

Таблица итераций Таблица 1.

k	x1	X2	X3	X4	Ek
1	-2,020272	-0.14705	2.568752	0.211236	0,69376533
2	-1,953853	-0.036345	2,642336	0,073243	0.08781591
3	-1,959725	-0.048092	2.63305366	0.0878948	0.17041907
4	-1,95946187	-0.047492	2.63430615	0.0874596	0.15810117
5	-1,95927921	-0.047563	2.63415981	0.0875070	0.15953549
6	- 1,9593008	-0.047555	2.63417685	0.0875017	0.15936833
7	-1,95929831	-0.047756	2.63417487	0.0875023	0.15938781
8	-1,95929861	-0.047556	2.63417511	0.0875023	0.15938554

Для нахождения решения системы нам понадобилось 8 итераций.

Решение системы: х1=-1,96 , х2=-0,05, х3= 2,63, х4=0,09

Погрешность: e= 0.00359794715263066

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



Заключение

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

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



Литература

1. Лекции по дисциплине «Вычислительная математика»

2. Игумнов Л.А., Литвинчук, С.Ю., Юрченко Т.В. Элементы численных методов в решении экономических задач: Учебное пособие

3. Бахвалов, Н.С. Численные методы

4. Гарнаев, А.Ю. Самоучитель VBA

5. Заварыкин, В.М. Численные методы: Учебное пособие для студентов физ.-мат. спец. пед. ин-тов

6. Исаков, В.Н. Элементы численных методов

7. Костомаров, Д.П. Вводные лекции по численным методам: Учебное пособие

8. Турчак, Л.И. Основы численных методов: Учебное пособие

9. Формалеев, В.Ф. Численные методы

Размещено на Allbest.ru

...