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

Линейные системы уравнений — реферат

Тема: «Линейные системы уравнений»

1. Уравнения, векторы, матрицы, алгебра

2. Умножение матриц как внешнее произведение векторов

3. Нормы векторов и матриц

4. Матрицы и определители

5. Собственные значения и собственные векторы

6. Ортогональные матрицы из собственных векторов

7. Функции с матричным аргументом

8. Вычисление проекторов матрицы

Пример использования числовых характеристик матриц

10. Оценка величины и нахождение собственных значений

1. Уравнения, векторы, матрицы, линейная алгебра

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

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

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

Здесь – неизвестные,

– заданные числа,

– заданные числовые коэффициенты.

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

список переменных – ,

список правых частей – и

матрицу коэффициентов – .

Первые два объекта в линейной алгебре называют вектором-строкой , а второй – квадратной матрицей.

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

Если рассмотреть i- тую строку исходной системы

,

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

.

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

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

.

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

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

Аксиоматическое построение линейной (векторной) алгебры с рассмотренными базовыми операциями позволило установить важные и полезные свойства, как самих объектов алгебры, так и их алгебраических выражений.

2. Умножение векторов и матриц

Среди n- мерных векторов и векторных операций над ними важно выделить сумму n векторов, умноженных на числовые константы:

,

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

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

Среди матриц размера и операций с ними в первую очередь необходимо отметить операцию умножения матрицы на матрицу. Необходимость введения операции умножения матриц возникает уже при первом взгляде на полученную векторную форму записи линейного уравнения . Векторы слева и справа имеют равные компоненты. Так как коэффициенты в строках матрицы в общем произвольны по величине, то соответствующие компоненты вектора x не обязаны быть равными компонентам вектора y . Последнее означает, что умножение вектора x на матрицу A вызвало изменение длины и направления вектора x . Если аналогичное преобразование выполняется над вектором правой части до решения уравнения, то вектор левой части должен быть преобразован так же:

.

Фактически мы имеем дело с заменой системы координат. Рассмотрим методику вычисления коэффициентов результирующей матрицы уравнения:

,

где – элемент матрицы С , равный скалярному произведению вектор-строки матрицы В на вектор-столбец матрицы А .

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

3. Нормы векторов и матриц

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

,

где – компоненты вектора ,

– евклидова норма вектора, его длина.

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

Деление вектора на величину его нормы называют нормированием , т.е. приведением вектора к единичной длине.

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

,

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

.

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

4. Матрицы и определители

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

Учитывая это свойство и зная, что определитель единичной матрицы det(E )=1, можно найти матрицу B и ее определитель из уравнения:

откуда следует, что и .

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

где – транспонированная матрица A ,

n – размер квадратной матрицы A ,

– матрица перестановки строк или столбцов,

s, c= 0,1,…, n – число выполненных перестановок строк и / или столбцов.

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

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

Классический способ вычисления обратной матрицы использует определители и осуществляется по формуле:

,

где – алгебраическое дополнение, а – минор матрицы A , получаемый вычислением определителя матрицы A , в которой вычеркнуты j- тая строка и i- тый столбец.

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

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

5. Собственные значения и собственные векторы

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

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

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

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

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

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

Важным свойством характеристического уравнения матрицы A является то, что согласно теореме Гамильтона-Кели, матрица A удовлетворяет ему:

где – k- тая степень матрицы.

Подставляя каждое в однородную систему, получим векторно-матричные уравнения для нахождения векторов или векторов-строк . Эти векторы называются соответственно правыми собственными векторами и левыми собственными векторами матрицы.

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

Если все собственные числа различны, то собственные векторы матрицы A образуют систему n линейно независимых векторов таких, что

6. Ортогональные матрицы из собственных векторов

Из правых собственных векторов можно составить матрицу T, а из левых – матрицу , которые обладают уникальными свойствами по отношению к матрице A .

Умножив матрицу A слева на матрицу , а справа – на матрицу T , после несложных преобразований получим:

.

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

Поэтому, результатом преобразования матрицы A будет диагональная матрица с собственными значениями, расположенными на диагонали:

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

Последнее показывает, что умножение матрицы A на слева и на S справа, где S – произвольная не особая матрица, преобразует ее в некоторую матрицу B , которая имеет определитель, равный определителю матрицы A . Такие преобразования матриц называют эквивалентными (подобными ).

Продолжая использовать T- матрицу, несложно получить следующие важные результаты:

.

7. Функции с матричным аргументом

Пусть теперь задана некоторая матричная функция от матрицы A :

.

С другой стороны очевидно и обратное

,

где – матрица с одной единицей на i -том месте диагонали ( ).

где – проекторы матрицы A , образуемые умножением одноименных правых и левых собственных векторов по правилам умножения прямоугольных матриц с размерами соответственно и . Сумма проекторов .

Проекторы обладают свойствами идемпотентных матриц , т.е. матриц, все степени которых равны первой. Для невырожденных проекторов ( ) матрицы A ( ) справедливо:

Представление функции от матрицы A в виде взвешенной суммы проекций называется спектральным разложением матричной функции по собственным значениям матрицы A :

.

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

8. Вычисление проекторов матрицы

Проекторы матрицы можно также вычислить, воспользовавшись интерполяционным многочленом Лагранжа с матричным аргументом:

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

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

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

где – значения i -тых произ-водных функции в точках, соответствующих различным (не кратным) корням характеристического многочлена,

– число кратных корней ,

– проекторы кратных корней, в выражении которых содержатся

– проекторы различных корней.

9. Пример использования числовых характеристик матриц

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

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

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

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

Откуда последовательно находятся коэффициенты :

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

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

,

где — матрица, в общем случае комплексно сопряженная с матрицей

, составленной из заданных векторов.

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

Для заданного выше набора векторов определитель произведения матрицы X на транспонированную X * будет равен

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

После нормирования векторы образуют правую систему собственных векторов. Транспонированная Т -матрица с этими векторами есть -матрица ( ); ее строки являются собственными левосторонними векторами:

.

Внешнее (матричное) произведение каждого нормированного вектора самого на себя дает нам проекторы искомой матрицы:

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

.

Аналогично получается обратная матрица:

.

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

.

10. Оценка величины и нахождение собственных значений

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

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

.

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

Характеристическое уравнение матрицы A с кратным корнем можно записать в виде

.

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

.

Особенности в части определения собственных значений и векторов обычно возникают в несимметричных матрицах ( ). Некоторые из них никакими подобными преобразованиями не удается свести к диагональной. Например, не поддаются диагонализации матрицы n- го порядка, которые не имеют n линейно независимых собственных векторов. Однако любая матрица A размера с помощью преобразования подобия может быть приведена к прямой сумме жордановых блоков или к канонической жордановой форме :

,

где A – произвольная матрица размера ;

– жорданов блок размера ;

V – некоторая невырожденная матрица размера .

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

.

Если выразить матрицу V в форме вектора с компонентами в виде векторов-столбцов , то из равенства AV=VJ для каждого жорданового блока следует соотношение

.

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

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

Один из возможных подходов к решению несимметричных линейных систем состоит в замене исходной системы эквивалентной системой:

.

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

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

Итак, основными алгебраическими системами уравнений можно считать неоднородные системы уравнений с симметричными матрицами коэффициентов.

1. Вержбицкий В.М. Основы численных методов: Учебник для вузов – 3-е изд. М: Высшая школа, 2009. – 840 с.

2. Самарcкий А.А. Задачи и упражнения по численным методам. Изд. 3 Изд-во: КомКнига, ЛКИ, 2006. – 208 с.

3. Турчак Л.И., Плотников П.В. Основы численных методов. Изд-во: ФИЗМАТЛИТ®, 2003. – 304 с.

4. Хеннер Е.К., Лапчик М.П., Рагулина М.И. Численные методы. Изд-во: «Академия/Academia», 2004. – 384c.

Реферат: Численные методы решения систем линейных алгебраических уравнений

Введение

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

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

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

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

Под численными методами подразумеваются методы решения задач, сводящиеся к арифметическим и некоторым логическим действиям над числами, т.е. к тем действиям, которые выполняет ЭВМ.

В настоящее время появилось значительное число различных программных продуктов (MathCAD, MathLABи т.д.), с помощью которых, задавая только входные данные, можно решить значительное число задач.

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

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

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

Предметом исследования, является выявление эффективности и сравнительная характеристика методов.

· изучить и проанализировать литературу по проблемам численных методов;

· изучить научную и учебную литературу по теме «Численные методы решения систем линейных алгебраических уравнений;

· определить основные этапы изучения темы «Численные методы решения систем линейных алгебраических уравнений»;

· продемонстрировать на примерах использование методов.

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

Во введении обоснована актуальность темы исследования, определены объект, предмет, проблема и задачи исследования.

В первой главе изучается теория и терминология численных методов с примерами и пояснениями.

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

В заключении подведены итоги и сделаны основные выводы.

Глава I. Теоретические основы исследования

§1 ЧИСЛЕННЫЕ МЕТОДЫ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Получим нули под главной диагональю в первом столбце расширенной матрицы. Для получения нуля в элементе 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. При этом все преобразования проводятся над так называемой расширенной матрицей системы, которую и приводят к верхнее — треугольному виду в прямом ходе метода.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.4 Итерация Якоби

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

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

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

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

Покажем, что если начать с точки 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):

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

1.5 Итерация Гаусса-Зейделя

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

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

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

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

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

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

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

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

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

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

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

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

Существуют два типа ме­тодов — прямые и итерационные. Мы рассматриваем прежде всего метод исключения Гаусса для систем об­щего вида и варианты — метод прогонки и методы мат­ричной прогонки для систем специального вида (с трех-диагональной или блочно-трех диагональной матрицами). Это — прямые методы. Их эффективность зависит от по­рядка системы n структуры матрицы.

При изучении итерационных методов мы трактуем си­стему уравнений как операторное уравнение первого ро­да Au = f и излагаем общую теорию итерационных ме­тодов для операторных уравнений при минимальных предположениях относительно оператора А. Общая тео­рия позволяет доказать сходимость итераций для метода Зейделя и метода верхней релаксации при минимальных ограничениях на оператор А. Рассмотрены два класса методов: 1) для случая, когда известны границы γ_i > О и γ₂ >= γ₁ спектра оператора А в некотором энергетиче­ском пространстве H_D ; 2) для случая, когда границы γ₁ и γ₂ неизвестны. Весьма эффективным является попере­менно-треугольный метод.

Основная задача линейной ал­гебры — решение системы уравнений

Будем предполагать, что матрица А невырождена, так что уравнение Аи = 0 имеет только триви­альное решение, и система (1) имеет единственноерешение

В курсе линейной алгебры решение системы (1) обыч­но выражают по формулам Крамера в виде отношений определителей. Для численного решения системы (1) эти формулы непригодны, так как они требуют вычисления N +1 определителей, что требует большого числа дей­ствий (порядка N! арифметических операций). Даже при выборе наилучшего метода вычисление одного определи­теля требует примерно такого же времени, что и реше­ние системы линейных уравнений современными числен­ными методами. Кроме того, следует иметь в виду, что вычисления по формулам Крамера часто ведут к боль­шим ошибкам округлений.

Особенность большинства численных методов для (1) состоит в отказе от нахождения обратной матрицы. Ос­новное требование к методу решения — минимум числа арифметических действий, достаточных для отыскания приближенного решения с заданной точностью е>0 (экономичность численного метода).

Выбор того или иного численного метода зависит от многих обстоятельств — от имеющихся программ, от вида матрицы А, от типа расчета и др. Поясним слова «тип расчета». Возможны разные постановки задачи:

1) найти решение одной конкретной задачи (1);

2) найти решение нескольких вариантов задачи (1) с одной и той же матрицей А и разными правыми частями. Может оказаться, что неоптимальный для одной задачи метод является весьма эффективным для мно­говариантного расчета.

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

При теоретических оценках каче­ства алгоритмов их сравнение проводится по числу q ( e ) арифметических действий, достаточных для нахождения решения задачи с заданной точностью е > 0 [15].

Метод Гаусса. Имеется несколько вычислительных вариантов метода Гаусса, основанного на идее последо­вательного исключения. Процесс решения системы ли­нейных алгебраических уравнений Ax = f (1) по методу Гаусса состоит из двух этапов.

Первый этап (прямой ход). Система (1) приво­дится к треугольному виду

Метод квадратного корня. Этот метод пригоден для систем

с эрмитовой (в действительном случае — симметричной) матрицей А. Матрица А разлагается в произведение

где S — верхняя треугольная, D — диагональная матрица. Решение уравнения Аu=fсводится к последователь­ному решению двух систем

Метод квадратного корня требует порядка N 2 /3 арифметических действий, т. е. при больших N он вдвое быстрее метода Гаусса и занимает вдвое меньше ячеек памяти. Это обстоятельство объясняется тем, что метод использует информацию о симметрии матрицы.

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

Перейдем к общему описанию метода итераций для системы линейных алгебраических уравнений

Для ее решения выбирается некоторое начальное приближение у₀ H и последовательно находятся приближенные решения (итерации) уравнения (1). Значение итерации y_{h +1} выражается через известные предыдущие итерации y_k , y_{k -1} ,… Если при вычислении y_{h +1} используется толь­ко одна предыдущая итерация y_h , то итерационный метод называют одношаговым (или двухслойным) методом; если же y_{k +1} выражается через две итерации y_k и y_{k -1} , то метод называется двухшаговым (или трехслойным). Мы будем рассматривать в основном одношаговые методы. Будем считать, что А: H -> H — линейный оператор в конеч­номерном пространстве H со скалярным произведе­нием (•, •).

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

(7), где А: Н -> Н — оператор исходного уравнения (1), В: Н -> Н — линейный оператор, имеющий обратный В -1 , k — номер итерации, τ₁ τ₂ , . τ_{k +1} , . — итерационные параметры, τ_{k +1} > 0. Оператор В может, вообще говоря, зависеть от номера k — для Для простоты изложения мы пред­полагаем всюду, что В не зависит от k .

Если В = Е — единичный оператор, то метод(8) называют явным: y_{h +1} находится по явной формуле

В общем случае, при В≠ Е, метод (7) называют не­явным итерационным методом: для определения y_{h +1} надо решить уравнение:

(9)

Естественно требовать, чтобы объем вычислений для ре­шения .системы By_{k +1} = F_k был меньше, чем объем вы­числений для прямого решения системы Au=f

Точность итерационного метода (7) характеризуется величиной погрешности z_h = у_к — и, т. е. разностью между решением уравнения (7) и точным решением и исход­ной системы линейных алгебраических уравнений. Под­становка y_k = z_k + u в (2) приводит к однородному урав­нению для погрешности:

§2 ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

2.1 Общие сведения

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

2.2.1 Описание метода

Рассмотрим СЛАУ вида

Ax = B, где А — матрица. (1)

Если эту систему удалось привести к виду x = Cx + D, то можно построить итерационную процедуру

x_k → x*, где х* — решение заданной системы.

В конечном варианте система будет имееть вид:

Условием сходимости для матрицы С выполняется, если сумма модулей коэффициентов меньше единицы по строкам или по столбцам, т.е.

, или .

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

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

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

В ней на главной диагонали матрицы С находятся нулевые элементы, остальные элементы выражаются по формулам:

Итерационный процесс продолжается до тех пор, пока значения х₁ ( k ), х₂ ( k ), х₃ ( k ) не станут близкими с заданной погрешностью к значениям х₁ ( k -1), х₂ ( k -1), х₃ ( k -1).

2.2.2 Решение СЛАУ методом простых итераций

Решить СЛАУ методом простых итераций с точностью .

Для удобства преобразуем систему к виду:

,

Принимаем приближение на 0-ом шаге:

,

,

На 1-м шаге выполняем следующее:

Подставляем принятые приближения в первоначальную систему уравнений

Смотрим не выполняется ли условие остановки итерационного процесса:

:

На 2-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса

:

На 3-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса

:

На 4-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса

:

На 5-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса:

:

На 6-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса:

:

Необходимая точность достигнута на 6-й итерации. Таким образом, итерационный процесс можно прекратить [14].

2.3 Метод Зейделя

2.3.1 Описание метода

В этом методе результаты, полученные на k-том шаге, используются на этом же шаге. На (k+1) — й итерации компоненты приближения вычисляются по формулам:

Этот метод применим к система уравнений в виде Ax=B при условии, что диагональный элемент матрицы коэффициентов A по модулю должен быть больше, чем сумма модулей остальных элементов соответствующей строки (столбца).

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

, либо

2.3.2 Решение СЛАУ методом Зейделя

Решить СЛАУ методом Зейделя с точностью .

Эту систему можно записать в виде:

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

Для удобства преобразуем систему к виду:

,

Принимаем приближение на 0-ом шаге:

На 1-м шаге выполняем следующее:

Подставляем принятые приближения в первоначальную систему уравнений

Смотрим не выполняется ли условие остановки итерационного процесса

:

На 2-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса

:

На 3-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса:

:

На 4-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса

:

Необходимая точность достигнута на 4-й итерации. Таким образом, итерационный процесс можно прекратить [9].

2.4 Сравнительный анализ

Можно заметить, что в методе Зейделя быстрее мы достигаемой нужной точности, в нашем случае в точность была достигнута на 4-й итерации, когда в методе простых итераций она была достигнута на 6-й итерации. Но в то же время в методе Зейделя ставится больше условий. Поэтому вначале нужно произвести иногда довольно трудоемкие преобразования. В таблице 4.1 приведены результаты решения СЛАУ методом простой итерации и методом Зейделя на различных шагах итерации:

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

Главная
• Список секций
• Математика
• РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

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

Автор работы награжден дипломом победителя I степени

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

Многие теоретические и практические вопросы приводят не к одному уравнению, а к целой системе уравнений с несколькими неизвестными. Особенно важен случай системы линейных алгебраических уравнений. Значение систем определяется не только тем, что они простейшие. На практике часто имеют дело с заведомо малыми величинами, старшими степенями которых можно пренебречь, так что уравнения с такими величинами сводятся в первом приближении к линейным. Не менее важно, что решение систем линейных уравнений составляет существенную часть при численном решении разнообразных прикладных задач. Ещё Г. Лейбниц (1693) обратил внимание на то, что при изучении систем линейных уравнений наиболее существенной является таблица, состоящая из коэффициентов, и показал, как из этих коэффициентов (в случае m = n) строить так называемые определители, при помощи которых исследуются системы линейных уравнений. Впоследствии такие матрицы стали предметом самостоятельного изучения, так как обнаружилось, что их роль не исчерпывается приложениями к теории систем линейных уравнений. Современная алгебра, понимаемая как учение об операциях над любыми математическими объектами, является одним из разделов математики, формирующих общие понятия и методы для всей математики. Для современной алгебры характерно то, что в центре внимания оказываются свойства операций, а не объектов, над которыми проводятся данные операции. Классическим разделом алгебры является линейная алгебра, т.е. теория векторных пространств и модулей, частью которых являются сформировавшиеся ещё в XIX веке теория линейных уравнений и теория матриц. Идеи и методы линейной алгебры применяются во многих разделах математики. Так, основным предметом изучения функционального анализа являются бесконечномерные векторные пространства.

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

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

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

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

Задачи:

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

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

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

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

Сделать вывод о проделанной работе.

II Основная часть2.1 Определение системы линейных алгебраических уравнений. Классификация систем

Под системой линейных алгебраических уравнений(СЛАУ) подразумевают систему

x_1, х₂,…. хn- неизвестные переменные, а_ij, i = 1,2. p, j = 1,2,…,n — коэффициенты, b₁,b₂. bp – свободные члены. [2]

Такую форму записи СЛАУ называют координатной.

Решением системы линейных алгебраических уравнений называют набор значений неизвестных переменных x₁ = a₁, x₂ = a₂,…, xn = an, обращающий все уравнения системы в тождества.

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

Если система уравнений решений не имеет, то она называется несовместной.

Если СЛАУ имеет единственное решение, то ее называют определенной; если решений больше одного, то – неопределенной.

Если свободные члены всех уравнений системы равны нулю b₁ = b₂ = … = bn = 0, то система называется однородной, в противном случае – неоднородной.

Если число уравнений системы равно числу неизвестных переменных и определитель ее основной матрицы не равен нулю, то такие СЛАУ будем называть элементарными. Такие системы уравнений имеют единственное решение, причем в случае однородной системы все неизвестные переменные равны нулю.

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

Основными методами решения элементарных систем линейных уравнений являются метод Крамера, матричный метод и метод Гаусса.

2.2 Матрицы и действия над ними. Алгебра матриц

Матрица размерами m × n – совокупность mn чисел, расположенных в виде прямоугольной таблицы из m строк и n столбцов, например (обозначим за А)

Числа, из которых состоит матрица, называются элементами матрицы. Они обозначаются буквами с двумя индексами: 1ый индекс указывает номер строки, а 2ой – номер столбца, в которых содержится этот элемент. В общем виде матрицы записываются в следующем виде:

Матрица A , имеющая i строк и j столбцов, называется матрицей размера i на j и обозначается A_ixj.

Элемент a_ij матрицы A = ij> стоит на пересечении i — ой строки и j — го столбца.

Если i = j, то матрица называется квадратной, а число строк (или столбцов) – её порядком.

Две матрицы, имеющие одинаковое количество строк и столбцов, называются матрицами одинакового типа. Две матрицы А = ij> и В = ij> одинакового типа называются равными, если a_ij = b_ij при всех i и j. [3]

Матрица, состоящая из одной строки (одного столбца), называется матрицей-строкой (матрицей-столбцом), а матрица, у которой все элементы а_ij = 0, – нулевой или нуль матрицей.

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

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

Квадратная матрица, все элементы которой, стоящие ниже (выше) главной диагонали, равны нулю, называется треугольной:

Диагональная матрица является частным случаем треугольной.

Транспонированием матрицы A=ij> называется операция, результатом которой является матрица A T = ji>.

Таким образом, если

Две матрицы А и В называются матрицами одного порядка, если они имеют одинаковое количество строк и одинаковое количество столбцов.

Матрицы А и В называются равными, если они одного порядка m´n, и a_{ij= bij},

где i = 1, 2, 3, …, m, а j = 1, 2, 3, …, n.

Умножение матрицы на число.

Умножение матрицы А на число λ приводит к умножению каждого элемента матрицы на число λ:

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

Свойства умножения матрицы на число:

2) (λμ)А = λ(μА) = μ(λА), где λ,μ R;

Сумма (разность) матриц.

Сумма (разность) определяется лишь для матриц одного порядка m´n.

Суммой (разностью) двух матриц А и В порядка m´n называется матрица С того же порядка, где c_ij = a_ij± b_ij(i = 1,2,3…m; j = 1,2,3…n).

Иными словами, матрица С состоит из элементов, равных сумме (разности) соответствующих элементов матриц А и В.

Из данных выше определений следуют свойства суммы матриц:

1) коммутативность А+В=В+А;

2) ассоциативность (А+В)+С=А+(В+С);

3) дистрибутивность к умножению на число λR: λ(А+В) = λА+λВ;

4) 0+А=А, где 0 – нулевая матрица;

5) А+(–А)=0, где (–А) – матрица, противоположная матрице А;

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

Произведением двух согласованных матриц A_mxn, а B_nxm, где

называется матрица С порядка m´k: С_mnx= A_mnx ∙ B_mnx, элементы которой вычисляются по формуле:

то есть элемент c_ij i –ой строки и j –го столбца матрицы С равен сумме произведений всех элементов i –ой строки матрицы А на соответствующие элементы j –го столбца матрицы В.

Рассмотрим свойства произведения матриц:

1) не коммутативность: АВ ≠ ВА, даже если А и В, и В и А согласованы. Если же АВ = ВА, то матрицы А и В называются коммутирующими (матрицы А и В в этом случае обязательно будут квадратными).

2) для любых квадратных матриц единичная матрица Е является коммутирующей к любой матрице А того же порядка, причем в результате получим ту же матрицу А, то есть АЕ = ЕА = А.

4) произведение двух матриц может равняться нулю, при этом матрицы А и В могут быть ненулевыми.

5) ассоциативность АВС=А(ВС)=(АВ)С:

6) дистрибутивность относительно сложения:

(А+В)∙С = АС + ВС, А∙(В + С)=АВ + АС.

8) λ(АּВ) = (λА)ּ В = Аּ (λВ), λR.

2.3 Определители квадратной матрицы и их свойства

Пусть А – квадратная матрица порядка n:

Каждой такой матрице можно поставить в соответствие единственное действительное число, называемое определителем (детерминантом) матрицы и обозначаемое

Отметим, что определитель существует только для квадратных матриц.

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

Определителем второго порядкаматрицы А_2х2 называется число, определяемое по правилу:

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

Из определения определителя второго порядка следуют его свойства:

1. Определитель не изменится при замене всех его строк соответствующими столбцами:

2. Знак определителя меняется на противоположный при перестановке строк (столбцов) определителя:

3. Общий множитель всех элементов строки (столбца) определителя можно вынести за знак определителя:

4. Если все элементы некоторой строки (столбца) определителя равны нулю, то определитель равен нулю.

5. Определитель равен нулю, если соответствующие элементы его строк (столбцов) пропорциональны:

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

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

так как по свойству 5.

Остальные свойства определителей рассмотрим ниже.

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

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

Схематически правило треугольника можно изобразить следующим образом:

Произведение элементов в первом определителе, которые соединены прямыми, берется со знаком «плюс»; аналогично, для второго определителя — соответствующие произведения берутся cо знаком «минус».

Правило Саррюса: справа от определителя дописывают первых два столбца и произведения элементов на главной диагонали и на диагоналях, ей параллельных, берут со знаком «плюс»; а произведения элементов побочной диагонали и диагоналей, ей параллельных, со знаком «минус»: [7]

Примеры расчета определителя с помощью правила Сюрраса и методом треугольников разобраны в Приложении 1.

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

Рассмотрим еще два очень важных свойства определителей.

Введем понятия минора и алгебраического дополнения.

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

Пример. Тогда, например

Алгебраическим дополнением элемента α_ijопределителя |A| называется его минор M_ij, взятый со знаком (-1) i+j . Алгебраическое дополнение будем обозначать A_ij, то есть

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

Теорема Лапласа. Определитель равен сумме всех произведений элементов какой-либо строки (столбца) на соответствующие алгебраические дополнения элементов этой строки (столбца).

Заметим, что данное свойство определителя есть не что иное, как определение определителя любого порядка. На практике его используют для вычисления определителя любого порядка. Как правило, прежде чем вычислять определитель, используя свойства 1 – 7, добиваются того, если это возможно, чтобы в какой-либо строке (столбце) были равны нулю все элементы, кроме одного, а затем раскладывают по элементам строки (столбца).

Девятое свойство определителя носит название теорема аннулирования:

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

Примеры вычислений определителя с помощью теоремы Лапласа и теоремы аннулирования представлены в Приложении 2 и Приложении 3 соответственно.

2.4 Обратная матрица

В теории чисел наряду с числом α определяют число, противоположное ему (-α) такое, что α +(- α ) = 0, и число, обратное ему , что .

Аналогично, в теории матриц мы уже ввели понятие противоположной матрицы, ее обозначение (– А).

Обратной матрицейдля квадратной матрицы А порядка n называется матрица , если выполняются равенства

Где Е – единичная матрица порядка n.

Обратная матрица существует только для квадратных невырожденных матриц.

Квадратная матрица называется невырожденной(неособенной), если det A ≠ 0. Если же det A = 0, то матрица А называется вырожденной(особенной).

Невырожденная матрица А имеет единственную обратную матрицу А -1 .

Найдем определитель обратной матрицы. Так как определитель произведения двух матриц А и В одинакового порядка равен произведению определителей этих матриц, т. е. , следовательно, произведение двух невырожденных матриц АВ есть невырожденная матрица.[4]

Определитель обратной матрицы есть число, обратное определителю исходной матрицы.

Отметим ряд особых свойств обратной матрицы:

1) для данной матрицы А ее обратная матрица А -1 является единственной;

2) если существует обратная матрица А -1 , то правая обратная и левая обратная матрицы совпадают с ней;

3) особенная (вырожденная) квадратная матрица не имеет обратной матрицы.

Основные свойства обратной матрицы:

1) определитель обратной матрицы и определитель исходной матрицы являются обратными величинами;

2) обратная матрица произведения квадратных матриц равна произведению обратных матриц сомножителей, взятому в обратном порядке:

3) транспонированная обратная матрица равна обратной матрице от данной транспонированной матрицы:

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

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

Будем предполагать, что основная матрица A невырожденная. Тогда существует обратная матрица A -1 . Помножив матричное уравнение на матрицу A -1 , получим формулу, на которой основан матричный метод решения систем линейных уравнений:

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

Задана система трёх линейных уравнений с тремя неизвестными , где

Основная матрица системы уравнений невырожденная, поскольку её определитель отличен от нуля:

Обратную матрицу A -1 составим одним из методов, описанных выше:

По формуле матричного метода решения систем линейных уравнений получим

Матричный метод подходит для решения СЛАУ, в которых количество уравнений совпадает с числом неизвестных переменных и определитель основной матрицы системы отличен от нуля.[9] Если система содержит больше трех уравнений, то нахождение обратной матрицы требует значительных вычислительных усилий, поэтому, в этом случае целесообразно использовать для решения метод Гаусса.

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

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

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

где x₁, x₂, …, xn – неизвестные переменные, a_{i j} , i = 1, 2, …, n, j = 1, 2, …, n – числовые коэффициенты, b₁, b₂, …, bn — свободные члены. Решением СЛАУ называется такой набор значений x₁, x₂, …, xn, при которых все уравнения системы обращаются в тождества.

В матричном виде эта система может быть записана как, где

— основная матрица системы, ее элементами являются коэффициенты при неизвестных переменных, — матрица – столбец свободных членов, а — матрица – столбец неизвестных переменных. После нахождения неизвестных переменных x₁, x₂, …, xn, матрица становится решением системы уравнений и равенство A ⋅ X = B обращается в тождество A ⋅ X = B.

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

Метод Крамера основывается на двух свойствах определителя матрицы:

Определитель квадратной матрицы равен сумме произведений элементов какой-либо строки (столбца) на их алгебраические дополнения:

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

Итак, приступим к нахождению неизвестной переменной x₁. Для этого умножим обе части первого уравнения системы на А₁₁ , обе части второго уравнения – на А₂₁ , и так далее, обе части n-ого уравнения – на А_n1 (то есть, уравнения системы умножаем на соответствующие алгебраические дополнения первого столбца матрицы А):

Сложим все левые части уравнения системы, сгруппировав слагаемые при неизвестных переменных x₁, x₂, …, xn, и приравняем эту сумму к сумме всех правых частей уравнений:

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

и предыдущее равенство примет вид

Аналогично находим x₂. Для этого умножаем обе части уравнений системы на алгебраические дополнения второго столбца матрицы А:

Складываем все уравнения системы, группируем слагаемые при неизвестных переменных x₁, x₂, …, xn и применяем свойства определителя:

Аналогично находятся оставшиеся неизвестные переменные.

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

Если система линейных алгебраических уравнений однородная, то есть b₁=b₂=…=bn=0, то она имеет лишь тривиальное решение =x₂=…=xn=0 (при |A|≠0). Действительно, при нулевых свободных членах все определители будут равны нулю, так как будут содержать столбец нулевых элементов. Следовательно, формулы дадут x₁=x₂=…=xn=0 .

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

Вычисляем определитель основной матрицы системы

и убеждаемся, что он отличен от нуля.

которые являются определителями матриц, полученных из матрицы А заменой k-ого столбца (k = 1, 2, …, n) на столбец свободных членов.

Выполняем проверку результатов, подставляя x₁, x₂, …, xn в исходную СЛАУ. Все уравнения системы должны обратиться в тождества. Можно также вычислить произведение матриц A ⋅ X, если в результате получилась матрица, равная B, то решение системы найдено верно. В противном случае в ходе решения была допущена ошибка.

Пример решения системы уравнений методом Крамера представлен в Приложении 4.

2.7 Метод Гаусса

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

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

Будем считать, что α₁₁≠0, так как мы всегда можем этого добиться перестановкой местами уравнений системы. Исключим неизвестную переменную x₁ из всех уравнений системы, начиная со второго. Для этого ко второму уравнению системы прибавим первое, умноженное на — , к третьему уравнению прибавим первое, умноженное на — , и так далее, к n-ому уравнению прибавим первое, умноженное на -. Система уравнений после таких преобразований примет вид

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

Далее действуем аналогично, но лишь с частью полученной системы

Будем считать, что (в противном случае мы переставим местами вторую строку с k-ой, где ). Приступаем к исключению неизвестной переменной x₂ из всех уравнений, начиная с третьего.

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

Таким образом, переменная x₂ исключена из всех уравнений, начиная с третьего.

Так продолжаем прямой ход метода Гаусса пока система не примет вид

С этого момента начинаем обратный ход метода Гаусса: вычисляем xn из последнего уравнения как , с помощью полученного значения xn находим x_n-1 из предпоследнего уравнения, и так далее, находим x₁ из первого уравнения.

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

Решение системы уравнений методом Гаусса представлено в Приложении 5.

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

Метод Гаусса позволяет установить совместность или несовместность системы линейных уравнений, а в случае ее совместности определить все решения (или одно единственное решение).[7]

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

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

Предположим, что мы выполняем прямой ход метода Гаусса, и мы подошли к моменту исключения неизвестной переменной x_k, а на каком-то предыдущем i-ом шаге (i z then