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

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

Введение

Идею общего метода решения систем линейных уравнений высказал Лейбниц в 1693 году. Она была реализована швейцарским математиком Крамером в 1752 году. Он сформулировал и обосновал правило, носящее теперь его имя, которое позволяет решать системы n линейных уравнений с неизвестными и буквенными коэффициентами. По правилу Крамера каждая неизвестная равна отношению двух определителей. Крамер, фактически, заложил основы теории определителей, хотя и не предложил для них удобного обозначения (это сделал в 1841 году А. Кэли). В 1772 году Вандермонд опубликовал обширное исследование определителей, один из которых носит теперь его имя. Систематическое изложение этой теории принадлежит Бине и Коши. Их труды по теории определителей относятся к периоду 1812-1815 гг.

Коэффициенты системы линейных уравнений и свободные члены удобно сводить в таблицы, называемые матрицами системы. Постепенно определители систем стали относить к матрицам систем. Матричный метод решения систем линейных уравнений впервые описан в древнекитайском трактате «Девять книг о математическом искусстве» (II век до н.э.). Система линейных уравнений в этом трактате записывается в виде матрицы, столбцы которой составлены из коэффициентов при неизвестных и свободных членов, и решается методом исключения, впоследствии заново сформулированном Гауссом в 1849 году. Этот метод естественно формулируется в виде правил преобразования так называемой расширенной матрицы системы.

Исследования Вейерштрасса и Фробениуса далеко продвинули теорию матриц, обогатив ее новыми понятиями и задачами. Фробениус, в частности, ввел понятие ранга матрицы (1877 г.). Используя это понятие, Кронекер и Капелли в лекциях 1883-91 гг. (Кронекер) и 1892 г. (Капелли) излагали теорему, дающую исчерпывающий ответ на вопрос о том, при каких условиях система линейных уравнений с неизвестными имеет решение.

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

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

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

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

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

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

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

Общий вид системы линейных алгебраических уравнений:

{\displaystyle {\begin{cases}a_{11}x_{1}+a_{12}x_{2}+\dots +a_{1n}x_{n}=b_{1}\\a_{21}x_{1}+a_{22}x_{2}+\dots +a_{2n}x_{n}=b_{2}\\\dots \\a_{m1}x_{1}+a_{m2}x_{2}+\dots +a_{mn}x_{n}=b_{m}\\\end{cases}}}

Здесь -количествоуравнений, - количествопеременных,{\displaystylex_{1},x_{2},\dots ,x_{n}} неизвестные, которыенадоопределить, коэффициенты {\displaystylea_{11},a_{12},\dots ,a_{mn}} исвободныечлены {\displaystyleb_{1},b_{2},\dots ,b_{m}} предполагаютсяизвестными. Индексы коэффициентов в системах линейных уравнений ({\displaystyle a_{ij}}) формируются по следующему соглашению: первый индекс обозначает номер уравнения, второй -- номер переменной, при которой стоит этот коэффициент.

Система называется однородной, если все её свободные члены равны нулю{\displaystyle b_{1}=b_{2}=\dots b_{m}=0}, иначе -- неоднородной.

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

Решение системы линейных алгебраических уравнений - совокупность n{\displaystyle n} чисел {\displaystyle c_{1},c_{2},\dots ,c_{n}}, таких что их соответствующая подстановка вместо {\displaystyle x_{1},x_{2},\dots ,x_{n}} в систему обращает все её уравнения в тождества.

Система называется совместной, если она имеет хотя бы одно решение, и несовместной, если у неё нет ни одного решения. Решения считаются различными, если хотя бы одно из значений переменных не совпадает. Совместная система с единственным решением называется определённой, при наличии более одного решения - недоопределённой.

Система линейных алгебраических уравнений может быть представлена в матричной форме как:

Или

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

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

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

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

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



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

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

Допустим и - ненулевые числа. Умножаем 1-е уравнение системы на , 2-е на и складываем их; уравнением, которое мы получили, заменяем 1-е уравнение системы. Далее 1-е уравнение начальной системы нужно умножить на - , 2-е - на и итогом этого заменяем 2-е уравнение. Таким образом, первые 2 уравнения заменяем уравнениями:

(,

(.

На параметры и наложим 2 условия: условие исключения из второго уравнения и условие нормировки.

Получаем:



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

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

Где

(,

(,

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

, ,

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

(,

(,

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

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

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

И т.д

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

линейная система уравнение вращение

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

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

;

;

.

Лемма 1. Матрица является ортогональной матрицей.



Лемма 2. Для всякого вектора , существует матрица

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

Доказательство. Достаточно положить

Лемма 3. Произведение матрицы элементарного вращения на вектор может быть вычислено за 4 умножения и 2 сложения.

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

,

При осуществлении вычислений по этим формулам надо выполнить 4 умножения и 2 сложения. линейное алгебраическое уравнение вращение

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

Лемма 5.Произведение матрицы элементарного вращения на матрицу размера может быть вычислено за умножений и сложений.

Доказательство. Пусть матрица есть произведение матрицы элементарного вращения на матрицу . Запишем матрицы

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

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

Листинг

#include<stdio.h>

#include<malloc.h>

#include<math.h>

#include<iostream>

usingnamespace std;

int main()

{

setlocale(LC_ALL, "russian");

int N = 3;

int i, j, k;

double** A;

double* x;

double c, s;

A = (double**)malloc(N * sizeof(double*));

x = (double*)malloc(N * sizeof(double));

for (i = 0; i < N; i++)

{

A[i] = (double*)malloc((N + 1) * sizeof(double));

for (j = 0; j < N + 1; j++)

{

A[i][j] = 0.0;

}

}

cout <<"Введите A[i,j]"<< endl;

for (i = 0; i < N; i++)

{

for (j = 0; j < N + 1; j++)

{

cout <<"A["<< i <<"]["<< j <<"]: ";

cin >> A[i][j];

}

}

cout <<"МатрицаА: "<< endl;

for (i = 0; i < N; i++)

{

for (j = 0; j < N + 1; j++)

{

cout << A[i][j] <<"\t";

}

cout << endl;

}

cout << endl;

cout << endl;

double d, b;

for (i = 0; i < N; i++)

{

for (j = i + 1; j < N; j++)

{

c = A[i][i] / sqrt(A[i][i] * A[i][i] + A[j][i] * A[j][i]);

s = A[j][i] / sqrt(A[i][i] * A[i][i] + A[j][i] * A[j][i]);

for (k = i; k < N + 1; k++)

{

d = A[i][k];

b = A[j][k];

A[i][k] = c * d + s * b;

A[j][k] = (-1.0) * s * d + c * b;

}

}

}

for (i = N - 1; i >= 0; i--)

{

x[i] = A[i][N];

for (j = N - 1; j > i; j--)

{

x[i] -= A[i][j] * x[j];

}

x[i] /= A[i][i];

}

for (i = 0; i < N; i++)

{

cout << x[i] << endl;

}

}



Практическая часть

Используя метод вращений решим систему уравнений:

1-ый шаг. Исключим из второго уравнения. Для этого вычислим и .

=0.857493

=0.514495

Преобразуя коэффициенты первого и второго уравнения, получим

Далее вычисли коэффициенты



=0.919087

=0.394055

Заменяя первое и третье уравнения их линейными комбинациями с коэффициентами , и , соответственно получим систему:

2-й шаг. В полученной системе ,

Поэтому:

==

Заменяя второе и третье уравнение системы их линейными комбинациями с коэффициентами , и , , то придём к системе:

Обратный ход даёт последовательные значения , =0.999994,



Заключение

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

Опыт практического применения метода вращений показывает, что независимо от порядка матрицы обычно требуется выполнить не более 4-5 циклов для максимального уменьшения суммы квадратов внедиагональных элементов. Однако ошибки округления оказывают основное влияние лишь на первых 2-3 циклах.

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



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

1)Богачёв К.Ю. Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений: Московский государственный университет имени М.В. Ломоносова механико-математический факультет, кафедр вычислительной математики, Москва 1998 г.

2) Амосов АЛ, Дубинекнй ЮЛ., Копченова Н.В. Вычислительные методы для инженеров: Учеб. пособие. -- М.: Высш. шк., 1994. -- 544 с:

3) https://vuzlit.ru/863720/metod_vrascheniy_resheniya_lineynyh_sistem

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