Блок схема для решения уравнения методом гаусса

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

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

Формально задача ставится следующим образом: решить систему:

где коэффициенты и известны, а переменные — искомые неизвестные.

Удобно матричное представление этой задачи:

где — матрица , составленная из коэффициентов , и — векторы-столбцы высоты .

Стоит отметить, что СЛАУ может быть не над полем действительных чисел, а над полем по модулю какого-либо числа , т.е.:

— алгоритм Гаусса работает и для таких систем тоже (но этот случай будет рассмотрен ниже в отдельном разделе).

Алгоритм Гаусса

Строго говоря, описываемый ниже метод правильно называть методом «Гаусса-Жордана» (Gauss-Jordan elimination), поскольку он является вариацией метода Гаусса, описанной геодезистом Вильгельмом Жорданом в 1887 г. (стоит отметить, что Вильгельм Жордан не является автором ни теоремы Жордана о кривых, ни жордановой алгебры — всё это три разных учёных-однофамильца; кроме того, по всей видимости, более правильной является транскрипция «Йордан», но написание «Жордан» уже закрепилось в русской литературе). Также интересно заметить, что одновременно с Жорданом (а по некоторым данным даже раньше него) этот алгоритм придумал Класен (B.-I. Clasen).

Базовая схема

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

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

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

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

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

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

Поиск опорного элемента (pivoting)

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

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

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

К счастью, для корректности метода достаточно одних только обменов строк (т.н. «partial pivoting», в отличие от «full pivoting», когда обмениваются и строки, и столбцы). Но какую же именно строку следует выбирать для обмена? И правда ли, что поиск опорного элемента надо делать только тогда, когда текущий элемент нулевой?

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

Иными словами, перед выполнением -ой фазы алгоритма Гаусса-Жордана с эвристикой partial pivoting необходимо найти в -ом столбце среди элементов с индексами от до максимальный по модулю, и обменять строку с этим элементом с -ой строкой.

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

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

Вырожденные случаи

Итак, если останавливаться на алгоритме Гаусса-Жордана с partial pivoting, то, утверждается, если и система невырождена (т.е. имеет ненулевой определитель, что означает, что она имеет единственное решение), то описанный выше алгоритм полностью отработает и придёт к единичной матрице (доказательство этого, т.е. того, что ненулевой опорный элемент всегда будет находиться, здесь не приводится).

Рассмотрим теперь общий случай — когда и не обязательно равны. Предположим, что опорный элемент на -ом шаге не нашёлся. Это означает, что в -ом столбце все строки, начиная с текущей, содержат нули. Утверждается, что в этом случае эта -ая переменная не может быть определена, и является независимой переменной (может принимать произвольное значение). Чтобы алгоритм Гаусса-Жордана продолжил свою работу для всех последующих переменных, в такой ситуации надо просто пропустить текущий -ый столбец, не увеличивая при этом номер текущей строки (можно сказать, что мы виртуально удаляем -ый столбец матрицы).

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

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

Впрочем, проще это проверить явной подстановкой найденного решения: всем независимыми переменным присвоить нулевые значения, зависимым переменным присвоить найденные значения, и подставить это решение в текущую СЛАУ.

Реализация

Приведём здесь реализацию алгоритма Гаусса-Жордана с эвристикой partial pivoting (выбором опорного элемента как максимума по столбцу).

На вход функции передаётся сама матрица системы . Последний столбец матрицы — это в наших старых обозначениях столбец свободных коэффициентов (так сделано для удобства программирования — т.к. в самом алгоритме все операции со свободными коэффициентами повторяют операции с матрицей ).

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

В функции поддерживаются два указателя — на текущий столбец и текущую строку .

Также заводится вектор , в котором для каждой переменной записано, в какой строке должна она получиться (иными словами, для каждого столбца записан номер строки, в которой этот столбец отличен от нуля). Этот вектор нужен, поскольку некоторые переменные могли не «определиться» в ходе решения (т.е. это независимые переменные, которым можно присвоить произвольное значение — например, в приведённой реализации это нули).

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

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

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

Асимптотика

Оценим асимптотику полученного алгоритма. Алгоритм состоит из фаз, на каждой из которых происходит:

• поиск и перестановка опорного элемента — за время при использовании эвристики «partial pivoting» (поиск максимума в столбце)
• если опорный элемент в текущем столбце был найден — то прибавление текущего уравнения ко всем остальным уравнениям — за время

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

Таким образом, итоговая асимптотика алгоритма принимает вид .

При эта оценка превращается в .

Заметим, что когда СЛАУ рассматривается не в поле действительных чисел, а в поле по модулю два, то систему можно решать гораздо быстрее — об этом см. ниже в разделе «Решение СЛАУ по модулю».

Более точная оценка числа действий

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

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

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

Дополнения

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

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

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

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

Прямой ход алгоритма Гаусса — это алгоритм, аналогичный описанному выше алгоритму Гаусса-Жордана, за одним исключением: текущая переменная исключается не из всех уравнений, а только из уравнений после текущего. В результате этого действительно получается не диагональная, а треугольная матрица.

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

Таким образом, если , то данный алгоритм будет делать уже операций — что в два раза меньше алгоритма Гаусса-Жордана.

Решение СЛАУ по модулю

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

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

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

Особенно замечателен модуль, равный двум: для него все операции с матрицей можно производить очень эффективно. Например, отнимание одной строки от другой по модулю два — это на самом деле их симметрическая разность («xor»). Таким образом, весь алгоритм можно значительно ускорить, сжав всю матрицу в битовые маски и оперируя только ими. Приведём здесь новую реализацию основной части алгоритма Гаусса-Жордана, используя стандартный контейнер C++ «bitset»:

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

Если модуль произвольный (не обязательно простой), то всё становится несколько сложнее. Понятно, что пользуясь Китайской теоремой об остатках, мы сводим задачу с произвольным модулем только к модулям вида «степень простого». [ дальнейший текст был скрыт, т.к. это непроверенная информация — возможно, неправильный способ решения ]

Наконец, рассмотрим вопрос числа решений СЛАУ по модулю. Ответ на него достаточно прост: число решений равно , где — модуль, — число независимых переменных.

Немного о различных способах выбора опорного элемента

Как уже говорилось выше, однозначного ответа на этот вопрос нет.

Эвристика «partial pivoting», которая заключалась в поиске максимального элемента в текущем столбце, работает на практике весьма неплохо. Также оказывается, что она даёт практически тот же результат, что и «full pivoting» — когда опорный элемент ищется среди элементов целой подматрицы — начиная с текущей строки и с текущего столбца.

Но интересно отметить, что обе эти эвристики с поиском максимального элемента, фактически, очень зависят от того, насколько были промасштабированы исходные уравнения. Например, если одно из уравнений системы умножить на миллион, то это уравнение почти наверняка будет выбрано в качестве ведущего на первом же шаге. Это кажется достаточно странным, поэтому логичен переход к немного более сложной эвристике — так называемому «implicit pivoting».

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

Улучшение найденного ответа

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

В связи с этим, полученный алгоритмом Гаусса-Жордана ответ можно улучшить, применив к нему какой-либо простой численный метод — например, метод простой итерации.

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

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

Курсовая работа: Программирование системы уравнений

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

2 Решение системы уравнения методом Гаусса

3 Решение уравнения методами Ньютона, Хорд

4 Разработка блок схемы решения системы уравнения методом Гаусса

5 Разработка блок схемы решения уравнения методом Ньютона

6 Разработка блок схемы решения уравнения методом Хорд

7 Язык программирования Turbo Pascal

8 Разработка программы решения системы уравнения методом Гаусса при помощи Turbo Pascal

9 Разработка программы решения уравнения методом Ньютона при помощи Turbo Pascal

10 Разработка программы решения уравнения методом Хорд при помощи Turbo Pascal

Список используемых источников

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

Исторически первой была идея структурирования программ, в соответствии с которой программист должен был решить, какие именно процедуры он будет использовать в своей программе, а затем выбрать наилучшие алгоритмы для реализации этих процедур. Появление этой идеи было следствием недостаточной изученности алгоритмической стороны вычислительных процессов, столь характерной для ранних программных разработок (сороковые — пятидесятые годы). Типичным примером процедурно-ориентированного языка является Фортран – первый и всё ещё один из наиболее популярных языков программирования. Последовательное использование идеи процедурного структурирования программ привело к созданию обширных библиотек программирования, содержащих множество сравнительно небольших процедур, из которых, как из кирпичиков, можно строить «здание» программы.

По мере прогресса в области вычислительной математики акцент в программировании стал смещаться с процедур в сторону организации данных. Оказалось, что эффективная разработка сложных программ нуждается в действенных способах контроля правильности использования данных. Контроль должен осуществляться как на стадии компиляции, так и при прогоне программ, в противном случае, как показала практика, резко возрастают трудности создания крупных программных проектов. Отчётливое осознание этой проблемы привело к созданию Ангола-60, а позже Паскаля, Модулы-2, Си и множества других языков программирования, имеющих более или менее развитые структуры типов данных. Логическим следствием развития этого направления стал модульный подход к разработке программ, характеризующийся стремлением «спрятать» данные и процедуры внутри модуля.

Начиная с языка Симула-67, в программировании наметился новый подход, который получил название объектно-ориентированного программирования (в дальнейшем ООП). Его руководящая идея заключается в стремлении связать данные с обрабатывающими эти данные процедурами в единое целое – объект. Характерной чертой объектов является инкапсуляция (объединение) данных и алгоритмов их обработки, в результате чего и данные, и процедуры во многом теряют самостоятельное значение.

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

Цель решения задачи курсовой работы – автоматизация решения системы уравнения методом Гаусса, а так же решения уравнения методами Хорд и Ньютона.

Выходная информация задачи выводиться на экран монитора.

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

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

2 Решение системы уравнения методом Гаусса

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

Хотя в настоящее время данный метод повсеместно называется методом Гаусса, он был известен и до К. Ф. Гаусса. Первое известное описание данного метода — в китайском трактате «Математика в девяти книгах», составленном между I в. до н.э. и II в. н. э.

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

Пусть исходная система выглядит следующим образом

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

Переменные называются главными переменными. Все остальные называются свободными.

Если , то рассматриваемая система несовместна.

Предположим, что .

Перенесём свободные переменные за знаки равенств и поделим каждое из уравнений системы на свой коэффициент при самом левом (, где — номер строки):

,

где

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

1: Если в совместной системе все переменные главные, то такая система является определённой.

2: Если количество переменных в системе превосходит число уравнений, то такая система является либо неопределённой, либо несовместной.

Условие совместности.

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

Напомним, что рангом совместной системы называется ранг её основной матрицы (либо расширенной, так как они равны).

Алгоритм решения СЛАУ методом Гаусса подразделяется на два этапа.

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

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

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

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

Помимо аналитического решения СЛАУ, метод Гаусса также применяется для:

1) нахождения матрицы, обратной к данной (к матрице справа приписывается единичная такого же размера, что и исходная: , после чего приводится к виду единичной матрицы методом Гаусса—Жордана; в результате на месте изначальной единичной матрицы справа оказывается обратная к исходной матрица: );

2) определения ранга матрицы (согласно следствию из теоремы Кронекера—Капелли ранг матрицы равен числу её главных переменных);

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

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

Система т линейных уравнений с п неизвестными имеет вид:

b_i — свободные члены (или правые части)

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

Совместная система называется определенной , если она имеет единственное решение и неопределенной , если она имеет бесчисленное множество решений.

Две совместные системы называются равносильными , если они имеют одно и то же множество решений.

К элементарным преобразованиям системы отнесем следующее:

1) перемена местами двух любых уравнений;

2) умножение обеих частей любого из уравнений на произвольное число, отличное от нуля;

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

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

Элементарные преобразования системы используются в методе Гаусса.

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

( 1 )

1-ый шаг метода Гаусса.

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

( 2 )

где

Исключим х₁ из второго и третьего уравнений системы (1). Для этого вычтем из них уравнение (2), умноженное на коэффициент при х₁ (соответственно а ₂₁ и а ₃₁ ).

Система примет вид:

( 3 )

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

2-ой шаг метода Гаусса.

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

( 4 )

где

Из третьего уравнения системы (3) вычтем уравнение (4), умноженное на Получим уравнение:

Предполагая, что находим

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

(5)

Система вида (5) называется треугольной.

Процесс приведения системы (1) к треугольному виду (5) (шаги 1 и 2) называют прямым ходом метода Гаусса.

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

Для этого найденное значение х₃ подставляют во второе уравнение системы (5) и находят х₂ . Затем х₂ и х₃ подставляют в первое уравнение и находят х₁ .

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

Отсюда другое называние метода Гаусса – метод последовательного исключения неизвестных.

Если в ходе преобразований системы получается противоречивое уравнение вида 0 = b, где b¹ 0, то это означает, что система несовместна и решений не имеет.

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

Треугольная система имеет вид:

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

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

Такая система имеет бесчисленное множество решений. Чтобы найти эти решения, во всех уравнениях системы члены с неизвестными х_{k +1} , … , x_k переносят в правую часть. Эти неизвестные называются свободными и придают им произвольные значения. Из полученной треугольной системы находим х₁ , … , x_k , которые будут выражаться через свободные неизвестные. Подробнее об этом можно узнать в рекомендуемой литературе.

Рассмотренный метод Гаусса легко программируется на ЭВМ и является более экономичным (по числу действий), чем другие методы.

3 Решение уравнения методами Ньютона, Хорд

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

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

линейный уравнение хорда гаусс ньютон

, , если

, , если

, ,

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

Здесь вычисляются значения функции на концах отрезка и строится “хорда”, соединяющая точки (a, f(a)) и (b, f(b)). Точка пересечения ее с осью абсцисс

принимается за очередное приближение к корню. Анализируя знак f(z) в сопоставлении со знаком f(x) на концах отрезка, сужаем интервал до [a,z] или [z,b] и продолжаем процесс построения хорд до тех пор, пока разница между очередными приближениями не окажется достаточно малой (в пределах допустимой погрешности) |Z_n -Z_n-1 | * — корень уравнения, Z_n и Z_n+1 — очередные приближения, m и M – наименьшее.

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

(1)

где считаем малой величиной. Применяя формулу Тейлора, получим:

Внеся эту поправку в формулу (1), найдем следующее (по порядку) приближение корня

Геометрически метод Ньютона эквивалентен замене дуги кривой касательной, проведенной в некоторой точке кривой. В самом деле, положим для определенности, что при и (см. рис.).

Выберем, например, , для которого . Проведем касательную к кривой в точке B₀ с координатами.

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

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

Имеем

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

Тогда

или для любого шага n

.

В качестве начальной точки можно принять либо один из концов отрезка [a, b], либо точку внутри этого интервала. В первом случае рекомендуется выбирать ту границу, где выполняется условие

т.е. функция и ее вторая производная в точке должны быть одного знака.

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

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

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

4 Разработка блок схемы решения системы уравнения методом Гаусса

5 Разработка блок схемы решения уравнения методом Ньютона

6 Разработка блок схемы решения уравнения методом Хорд

7 Язык программирования Turbo Pascal

Turbo Pascal является реализацией Pascal’я. Самая первая версия Pascal быля разработана на кафедре информатики Стэндфордского университета швейцарским ученым Николаусом Виртом в 1968 году.

С момента появления Pascal на рынке продуктов прошло много времени прежде чем он получил всеобщее признание. В середине 80-х годов американской фирмой Borland International, Inc была создана реализация языка Pascal, известная и по сей день под именем Turbo Pascal. Эта фирма объединила очень быстрый компилятор с редактором текста и добавила к стандартному Паскалю мощное расширение, что способствовало успеху первой версии этого языка.

В 1985 году на рынке ПЭВМ появился язык программирования Турбо Паскаль (версия 3.0) с компилятором стандартного Паскаля. С тех пор Паскаль стал применяться в общеобразовательных, профессионально-технических школах и в сфере высшего образования в качестве «первого» языка программирования. Благодаря простоте использования язык Турбо Паскаль получил широкое распространение и в любительских кругах. Повышению популярности Турбо Паскаля способствовал набор небольших сопутствующих программ (Toos), позволяющих получать чрезвычайно компактную, быструю и легко читаемую программу. Эти качества Турбо Паскаля были высоко оценены и в среде профессиональных программистов. Встроенный редактор текста использует достаточно широко распространенную систему команд, берущую начало от пакета WordStar и хорошо знакомую каждому, кто интенсивно использует ПЭВМ.

В появившемся со временем пакете Турбо Паскаль 4.0 было устранено большинство подвергавшихся критике ограничений компилятора и была повышена производительность системы. Кроме того, новый компилятор версии 4.0 имел существенные отличия от предыдущей версии. Наиболее важным нововведением была ИNIТ-концепция, заимствованная из языка Модула-2. Это дало возможность реализовать в рамках ТП разработку крупных программных продуктов.

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

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

Кроме того, в ТП 5.0 были расширены возможности отладки программ и обеспечена возможность поддержки расширенной памяти в стандарте Lotus-Intel-Microsoft (SLIMS/EMS 4.0). Сокращение EMS обозначает Expanded Memory Specification (спецификация расширенной памяти). Нельзя путать этот вид дополнительной памяти с другим — Extended Memory. EMS имеется на обычных ПЭВМ класса XT, в то время как Extended Memory — только на машинах АТ-класса (с процессором 286, 386 и выше) при объеме памяти свыше 1 Мбайта.

В этой версии были также исправлены и улучшены библиотеки графических процедур, поставляемые вместе с пакетом ТП и обеспечивающие полную совместимость с графическими адаптерами класса VGA (Video Graphics Array).

В рамках версии ТП 5.5 были осуществлены дальнейшие преобразования в направлении улучшения технических характеристик пакета. Наряду с внутренними улучшениями и новыми возможностями встроенной справочной системы Help, а также большим набором учебных примеров, важным нововведением явилась реализация в языке концепции объектно-ориентированного программирования (ООП).

Через некоторое время на рынке появился ТП 6.0, в котором теоретическая концепция объектно-ориентированного программирования была реализована практически с полным набором объектов, которые могли использоваться для решения прикладных задач. Кроме того, реализация системы меню приведена в соответствие со стандартом SAA (Turbo Vision). В качестве практического примера использования новых возможностей был реализован текстовый редактор, встроенный в IDE

Integrated Development Environment — интегрированную инструментальную оболочку. При этом сторонники программирования на ТП 6.0 получили возможность не только работать со встроенным многооконным текстовым редактором, но и использовать мышь, которая значительно облегчает работу пользователя.

В 1992 году фирма Borland International представила пользователям очередную версию языка Паскаль — Турбо Паскаль 7.0. Наряду со всеми преимуществами, которые унаследованы от предыдущей версии (многооконный режим работы, возможность использования мыши, возможность использования языка программирования низкого уровня Ассемблер, возможность создавать объектно-ориентированные программы), в ТП 7.0 были произведены изменения и улучшения. Во-первых: появилась возможность выделять определенным цветом различные элементы исходного текста (зарезервированные слова, идентификаторы, числа и т. д.), позволяющая даже неопытным пользователям устранять ошибки на этапе ввода исходного текста. Во-вторых: язык программирования ТП 7.0 был расширен (появилась возможность использовать типизированный адресный оператор, открытые массивы и строки и т. д.), что предоставило пользователю дополнительные возможности при решении повседневных задач. В-третьих: был улучшен компилятор, вследствие чего «коды программ» стали более эффективными. В-четвертых: был улучшен интерфейс пользователя. Кроме того, в ТП 7.0 расширены возможности объектно-ориентированного программирования (в частности, расширены и улучшены возможности Turbo Vision).

8 Разработка программы решения системы уравнения методом Гаусса при помощи Turbo Pascal

A:array[1..N,1..N] of real = ((9.1, 5.6, 7.8),

Метода Гаусса: примеры решения СЛАУ

В данной статье мы:

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

Метод Гаусса — что это такое?

Метод Гаусса — это метод, который применяется при решении систем линейных алгебраических уравнений и имеет следующие преимущества:

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

Основные определения и обозначения

Есть система из р линейных уравнений с n неизвестными ( p может быть равно n ):

a 11 x 1 + a 12 x 2 + . . . + a 1 n x n = b 1 a 21 x 1 + a 22 x 2 + . . . + a 2 n x n = b 2 ⋯ a p 1 x 1 + a p 2 x 2 + . . . + a p n x n = b p ,

где x 1 , x 2 , . . . . , x n — неизвестные переменные, a i j , i = 1 , 2 . . . , p , j = 1 , 2 . . . , n — числа (действительные или комплексные), b 1 , b 2 , . . . , b n — свободные члены.

Если b 1 = b 2 = . . . = b n = 0 , то такую систему линейных уравнений называют однородной, если наоборот — неоднородной.

Решение СЛАУ — совокупность значения неизвестных переменных x 1 = a 1 , x 2 = a 2 , . . . , x n = a n , при которых все уравнения системы становятся тождественными друг другу.

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

Определенная СЛАУ — это такая система, которая имеет единственное решение. В случае, если решений больше одного, то такая система будет называться неопределенной.

Координатный вид записи:

a 11 x 1 + a 12 x 2 + . . . + a 1 n x n = b 1 a 21 x 1 + a 22 x 2 + . . . + a 2 n x n = b 2 ⋯ a p 1 x 1 + a p 2 x 2 + . . . + a p n x n = b p

Матричный вид записи: A X = B , где

A = a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋯ ⋯ ⋯ ⋯ a p 1 a p 2 ⋯ a p n — основная матрица СЛАУ;

X = x 1 x 2 ⋮ x n — матрица-столбец неизвестных переменных;

B = b 1 b 2 ⋮ b n — матрица свободных членов.

Расширенная матрица — матрица, которая получается при добавлении в качестве ( n + 1 ) столбца матрицу-столбец свободных членов и имеет обозначение Т .

T = a 11 a 12 ⋮ a 1 n b 1 a 21 a 22 ⋮ a 2 n b 2 ⋮ ⋮ ⋮ ⋮ ⋮ a p 1 a p 2 ⋮ a p n b n

Вырожденная квадратная матрица А — матрица, определитель которой равняется нулю. Если определитель не равен нулю, то такая матрица, а потом называется невырожденной.

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

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

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

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

Алгоритм метода Гаусса:

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

a 11 x 1 + a 12 x 2 + a 13 x 3 + . . . + a 1 n x n = b 1 a 21 x 1 + a 22 x 2 + a 23 x 3 + . . . + a 2 n x n = b 2 a 31 x 1 + a 32 x 2 + a 33 x 3 + . . . + a 3 n x n = b 3 ⋯ a n 1 x 1 + a n 2 x 2 + a n 3 x 3 + . . . + a n n x n = b n

Определитель матрицы не равен нулю.

1. a 11 не равен нулю — всегда можно добиться этого перестановкой уравнений системы;
2. исключаем переменную x 1 из всех уравнений систему, начиная со второго;
3. прибавим ко второму уравнению системы первое, которое умножено на — a 21 a 11 , прибавим к третьему уравнению первое умноженное на — a 21 a 11 и т.д.

После проведенных действий матрица примет вид:

a 11 x 1 + a 12 x 2 + a 13 x 3 + . . . + a 1 n x n = b 1 a ( 1 ) 22 x 2 + a ( 1 ) 23 x 3 + . . . + a ( 1 ) 2 n x n = b ( 1 ) 2 a ( 1 ) 32 x 2 + a ( 1 ) 33 x 3 + . . . + a ( 1 ) 3 n x n = b ( 1 ) 3 ⋯ a ( 1 ) n 2 x 2 + a ( 1 ) n 3 x 3 + . . . + a ( 1 ) n n x n = b ( 1 ) n ,

где a i j ( 1 ) = a i j + a 1 j ( — a i 1 a 11 ) , i = 2 , 3 , . . . , n , j = 2 , 3 , . . . , n , b i ( 1 ) = b i + b 1 ( — a i 1 a 11 ) , i = 2 , 3 , . . . , n .

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

a 11 x 1 + a 12 x 2 + a 13 x 3 + . . . + a 1 n x n = b 1 a ( 1 ) 22 x 2 + a ( 1 ) 23 x 3 + . . . + a ( 1 ) 2 n x n = b ( 1 ) 2 a ( 1 ) 32 x 2 + a ( 1 ) 33 x 3 + . . . + a ( 1 ) 3 n x n = b ( 1 ) 3 ⋯ a ( 1 ) n 2 x 2 + a ( 1 ) n 3 x 3 + . . . + a ( 1 ) n n x n = b ( 1 ) n

Считается, что a 22 ( 1 ) не равна нулю. Таким образом, приступаем к исключению неизвестной переменной x 2 из всех уравнений, начиная с третьего:

• к третьему уравнению систему прибавляем второе, которое умножено на — a ( 1 ) 42 a ( 1 ) 22 ;
• к четвертому прибавляем второе, которое умножено на — a ( 1 ) 42 a ( 1 ) 22 и т.д.

После таких манипуляций СЛАУ имеет следующий вид:

a 11 x 1 + a 12 x 2 + a 13 x 3 + . . . + a 1 n x n = b 1 a ( 1 ) 22 x 2 + a ( 1 ) 23 x 3 + . . . + a ( 1 ) 2 n x n = b ( 1 ) 2 a ( 2 ) 33 x 3 + . . . + a ( 2 ) 3 n x n = b ( 2 ) 3 ⋯ a ( 2 ) n 3 x 3 + . . . + a ( 2 ) n n x n = b ( 2 ) n ,

где a i j ( 2 ) = a ( 1 ) i j + a 2 j ( — a ( 1 ) i 2 a ( 1 ) 22 ) , i = 3 , 4 , . . . , n , j = 3 , 4 , . . . , n , b i ( 2 ) = b ( 1 ) i + b ( 1 ) 2 ( — a ( 1 ) i 2 a ( 1 ) 22 ) , i = 3 , 4 , . . . , n . .

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

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

a 11 x 1 + a 12 x 2 + a 13 x 3 + . . . + a 1 n x n = b 1 a ( 1 ) 22 x 2 + a ( 1 ) 23 x 3 + . . . + a ( 1 ) 2 n x n = b ( 1 ) 2 a ( 2 ) 33 x 3 + . . . + a ( 2 ) 3 n x n = b ( 2 ) 3 ⋯ a ( n — 1 ) n n x n = b ( n — 1 ) n

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

• вычисляем x n из последнего уравнения как x n = b n ( n — 1 ) a n n ( n — 1 ) ;
• с помощью полученного x n находим x n — 1 из предпоследнего уравнения и т.д., находим x 1 из первого уравнения.

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

3 x 1 + 2 x 2 + x 3 + x 4 = — 2 x 1 — x 2 + 4 x 3 — x 4 = — 1 — 2 x 1 — 2 x 2 — 3 x 3 + x 4 = 9 x 1 + 5 x 2 — x 3 + 2 x 4 = 4

Коэффициент a 11 отличен от нуля, поэтому приступаем к прямому ходу решения, т.е. к исключению переменной x 11 из всех уравнений системы, кроме первого. Для того, чтобы это сделать, прибавляем к левой и правой частям 2-го, 3-го и 4-го уравнений левую и правую часть первого, которая умножена на — a 21 a 11 :

— 1 3 , — а 31 а 11 = — — 2 3 = 2 3 и — а 41 а 11 = — 1 3 .

3 x 1 + 2 x 2 + x 3 + x 4 = — 2 x 1 — x 2 + 4 x 3 — x 4 = — 1 — 2 x 1 — 2 x 2 — 3 x 3 + x 4 = 9 x 1 + 5 x 2 — x 3 + 2 x 4 = 4 ⇔

⇔ 3 x 1 + 2 x 2 + x 3 + x 4 = — 2 x 1 — x 2 + 4 x 3 — x 4 + ( — 1 3 ) ( 3 x 1 + 2 x 2 + x 3 + x 4 ) = — 1 + ( — 1 3 ) ( — 2 ) — 2 x 1 — 2 x 2 — 3 x 3 + x 4 + 2 3 ( 3 x 1 + 2 x 2 + x 3 + x 4 ) = 9 + 2 3 ( — 2 ) x 1 + 5 x 2 — x 3 + 2 x 4 + ( — 1 3 ) ( 3 x 1 + 2 x 2 + x 3 + x 4 ) = 4 + ( — 1 3 ) ( — 2 ) ⇔

⇔ 3 x 1 + 2 x 2 + x 3 + x 4 = — 2 — 5 3 x 2 + 11 3 x 3 — 4 3 x 4 = — 1 3 — 2 3 x 2 — 7 3 x 3 + 5 3 x 4 = 23 3 13 3 x 2 — 4 3 x 3 + 5 3 x 4 = 14 3

Мы исключили неизвестную переменную x 1 , теперь приступаем к исключению переменной x 2 :

— a 32 ( 1 ) a 22 ( 1 ) = — — 2 3 — 5 3 = — 2 5 и а 42 ( 1 ) а 22 ( 1 ) = — 13 3 — 5 3 = 13 5 :

3 x 1 + 2 x 2 + x 3 + x 4 = — 2 — 5 3 x 2 + 11 3 x 3 — 4 3 x 4 = — 1 3 — 2 3 x 2 — 7 3 x 3 + 5 3 x 4 = 23 3 13 3 x 2 — 4 3 x 3 + 5 3 x 4 = 14 3 ⇔

⇔ 3 x 1 + 2 x 2 + x 3 + x 4 = — 2 — 5 3 x 2 + 11 3 x 3 — 4 3 x 4 = — 1 3 — 2 3 x 2 — 7 3 x 3 + 5 3 x 4 + ( — 2 5 ) ( — 5 3 x 2 + 11 3 x 3 — 4 3 x 4 ) = 23 3 + ( — 2 5 ) ( — 1 3 ) 13 3 x 2 — 4 3 x 3 + 5 3 x 4 + 13 5 ( — 5 3 x 2 + 11 3 x 3 — 4 3 x 4 ) = 14 3 + 13 5 ( — 1 3 ) ⇔

⇔ 3 x 1 + 2 x 2 + x 3 + x 4 = — 2 — 5 3 x 2 + 11 3 x 3 — 4 3 x 4 = — 1 3 — 19 5 x 3 + 11 5 x 4 = 39 5 41 5 x 3 — 9 5 x 4 = 19 5

Для того чтобы завершить прямой ход метода Гаусса, необходимо исключить x 3 из последнего уравнения системы — а 43 ( 2 ) а 33 ( 2 ) = — 41 5 — 19 5 = 41 19 :

3 x 1 + 2 x 2 + x 3 + x 4 = — 2 — 5 3 x 2 + 11 3 x 3 — 4 3 x 4 = — 1 3 — 19 5 x 3 + 11 5 x 4 = 39 5 41 5 x 3 — 9 5 x 4 = 19 5 ⇔

3 x 1 + 2 x 2 + x 3 + x 4 = — 2 — 5 3 x 2 + 11 3 x 3 — 4 3 x 4 = — 1 3 — 19 5 x 3 + 11 5 x 4 = 39 5 41 5 x 3 — 9 5 x 4 + 41 19 ( — 19 5 x 3 + 11 5 x 4 ) = 19 5 + 41 19 39 5 ⇔

⇔ 3 x 1 + 2 x 2 + x 3 + x 4 = — 2 — 5 3 x 2 + 11 3 x 3 — 4 3 x 4 = — 1 3 — 19 5 x 3 + 11 5 x 4 = 39 5 56 19 x 4 = 392 19

Обратный ход метода Гаусса:

• из последнего уравнения имеем: x 4 = 392 19 56 19 = 7 ;
• из 3-го уравнения получаем: x 3 = — 5 19 ( 39 5 — 11 5 x 4 ) = — 5 19 ( 39 5 — 11 5 × 7 ) = 38 19 = 2 ;
• из 2-го: x 2 = — 3 5 ( — 1 3 — 11 3 x 4 + 4 3 x 4 ) = — 3 5 ( — 1 3 — 11 3 × 2 + 4 3 × 7 ) = — 1 ;
• из 1-го: x 1 = 1 3 ( — 2 — 2 x 2 — x 3 — x 4 ) = — 2 — 2 × ( — 1 ) — 2 — 7 3 = — 9 3 = — 3 .

Ответ: x 1 = — 3 ; x 2 = — 1 ; x 3 = 2 ; x 4 = 7

Найти решение этого же примера методом Гаусса в матричной форме записи:

3 x 1 + 2 x 2 + x 3 + x 4 = — 2 x 1 — x 2 + 4 x 3 — x 4 = — 1 — 2 x 1 — 2 x 2 — 3 x 3 + x 4 = 9 x 1 + 5 x 2 — x 3 + 2 x 4 = 4

Расширенная матрица системы представлена в виде:

x 1 x 2 x 3 x 4 3 2 1 1 1 — 1 4 — 1 — 2 — 2 — 3 1 1 5 — 1 2 — 2 — 1 9 4

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

Преобразование матрицы начинается с превращения всех элементов нулевые. Для этого к элементам 2-ой, 3-ей и 4-ой строк прибавляем соответствующие элементы 1-ой строки, которые умножены на — a 21 a 11 = — 1 3 , — a 31 a 11 = — — 2 3 = 2 3 и н а — а 41 а 11 = — 1 3 .

Дальнейшие преобразования происходит по такой схеме: все элементы во 2-ом столбце, начиная с 3-ей строки, становятся нулевыми. Такой процесс соответствует процессу исключения переменной . Для того, чтобы выполнить этой действие, необходимо к элементам 3-ей и 4-ой строк прибавить соответствующие элементы 1-ой строки матрицы, которая умножена на — а 32 ( 1 ) а 22 ( 1 ) = — 2 3 — 5 3 = — 2 5 и — а 42 ( 1 ) а 22 ( 1 ) = — 13 3 — 5 3 = 13 5 :

x 1 x 2 x 3 x 4 3 2 1 1 | — 2 0 — 5 3 11 3 — 4 3 | — 1 3 0 — 2 3 — 7 3 5 3 | 23 3 0 13 3 — 4 3 5 3 | 14 3

x 1 x 2 x 3 x 4

3 2 1 1 | — 2 0 — 5 3 11 3 — 4 3 | — 1 3 0 — 2 3 + ( — 2 5 ) ( — 5 3 ) — 7 3 + ( — 2 5 ) 11 3 5 3 + ( — 2 5 ) ( — 4 3 ) | 23 3 + ( — 2 5 ) ( — 1 3 ) 0 13 3 + 13 5 ( — 5 3 ) — 4 3 + 13 5 × 11 3 5 3 + 13 5 ( — 4 3 ) | 14 3 + 13 5 ( — 1 3 )

x 1 x 2 x 3 x 4

3 2 1 1 | — 2 0 — 5 3 11 3 — 4 3 | — 1 3 0 0 — 19 5 11 5 | 39 5 0 0 41 5 — 9 5 | 19 5

Теперь исключаем переменную x 3 из последнего уравнения — прибавляем к элементам последней строки матрицы соответствующие элементы последней строки, которая умножена на а 43 ( 2 ) а 33 ( 2 ) = — 41 5 — 19 5 = 41 19 .

x 1 x 2 x 3 x 4 3 2 1 1 | — 2 0 — 5 3 11 3 — 4 3 | — 1 3 0 0 — 19 5 11 5 | 39 5 0 0 41 5 — 9 5 | 19 5

x 1 x 2 x 3 x 4

3 2 1 1 | — 2 0 — 5 3 11 3 — 4 3 | — 1 3 0 0 — 19 5 11 5 | 39 5 0 0 41 5 + 41 19 ( — 19 5 ) — 9 5 + 41 19 × 11 5 | 19 5 + 41 19 × 39 5

x 1 x 2 x 3 x 4

3 2 1 1 | — 2 0 — 5 3 11 3 — 4 3 | — 1 3 0 0 — 19 5 11 5 | 39 5 0 0 0 56 19 | 392 19

Теперь применим обратных ход метода. В матричной форме записи такое преобразование матрицы, чтобы матрица, которая отмечена цветом на изображении:

x 1 x 2 x 3 x 4 3 2 1 1 | — 2 0 — 5 3 11 3 — 4 3 | — 1 3 0 0 — 19 5 11 5 | 39 5 0 0 0 56 19 | 392 19

стала диагональной, т.е. приняла следующий вид:

x 1 x 2 x 3 x 4 3 0 0 0 | а 1 0 — 5 3 0 0 | а 2 0 0 — 19 5 0 | а 3 0 0 0 56 19 | 392 19 , где а 1 , а 2 , а 3 — некоторые числа.

Такие преобразования выступают аналогом прямому ходу, только преобразования выполняются не от 1-ой строки уравнения, а от последней. Прибавляем к элементам 3-ей, 2-ой и 1-ой строк соответствующие элементы последней строки, которая умножена на

— 11 5 56 19 = — 209 280 , н а — — 4 3 56 19 = 19 42 и н а — 1 56 19 = 19 56 .

x 1 x 2 x 3 x 4 3 2 1 1 | — 2 0 — 5 3 11 3 — 4 3 | — 1 3 0 0 — 19 5 11 5 | 39 5 0 0 0 56 19 | 392 19

x 1 x 2 x 3 x 4

3 2 1 1 + ( — 19 56 ) 56 19 | — 2 + ( — 19 56 ) 392 19 0 — 5 3 11 3 — 4 3 + 19 42 × 56 19 | — 1 3 + 19 42 × 392 19 0 0 — 19 5 11 5 + ( — 209 280 ) 56 19 | 39 5 + ( — 209 280 ) 392 19 0 0 0 56 19 | 392 19

x 1 x 2 x 3 x 4

3 2 1 0 | — 9 0 — 5 3 11 3 0 | 9 0 0 — 19 5 0 | — 38 5 0 0 0 56 19 | 392 19

Далее прибавляем к элементам 2-ой и 1-ой строк соответствующие элементы 3-ей строки, которые умножены на

— 11 3 — 19 5 = 55 57 и н а — 1 — 19 5 = 5 19 .

x 1 x 2 x 3 x 4 3 2 1 0 | — 9 0 — 5 3 11 3 0 | 9 0 0 — 19 5 0 | — 38 5 0 0 0 56 19 | 392 19

x 1 x 2 x 3 x 4

3 2 1 + 5 19 ( — 19 5 ) 0 | — 9 + 5 19 ( — 38 5 ) 0 — 5 3 11 3 + 55 57 ( — 19 5 ) 0 | 9 + 55 57 ( — 38 5 ) 0 0 — 19 5 0 | — 38 5 0 0 0 56 19 | 392 19

x 1 x 2 x 3 x 4

3 2 1 0 | — 11 0 — 5 3 0 0 | 5 3 0 0 — 19 5 0 | — 38 5 0 0 0 56 19 | 392 19

На последнем этапе прибавляем элементы 2-ой строки к соответствующим элементам 1-ой строки, которые умножены на — 2 — 5 3 = 6 5 .

x 1 x 2 x 3 x 4 3 2 1 0 | — 11 0 — 5 3 0 0 | 5 3 0 0 — 19 5 0 | — 38 5 0 0 0 56 19 | 392 19

x 1 x 2 x 3 x 4

3 2 + 6 5 ( — 5 3 ) 0 0 | — 11 + 6 5 × 5 3 ) 0 — 5 3 0 0 | 5 3 0 0 — 19 5 0 | — 38 5 0 0 0 56 19 | 392 19

x 1 x 2 x 3 x 4

3 0 0 0 | — 9 0 — 5 3 0 0 | 5 3 0 0 — 19 5 0 | — 38 5 0 0 0 56 19 | 392 19

Полученная матрица соответствует системе уравнений

3 x 1 = — 9 — 5 3 x 2 = 5 3 — 19 5 x 3 = — 38 5 56 19 x 4 = 392 19 , откуда находим неизвестные переменные.

Ответ: x 1 = — 3 , x 2 = — 1 , x 3 = 2 , x 4 = 7 . ​​​

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

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

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

В принципе, метод исключения неизвестных при таких СЛАУ остается таким же, однако есть несколько моментов, на которых необходимо заострить внимание.

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

Если мы исключаем из 2-го и 3-го уравнения x 1 , то ситуация оказывается следующей:

x 1 + 2 x 2 — x 3 + 3 x 4 = 7 2 x 1 + 4 x 2 — 2 x 3 + 6 x 4 = 14 x — x + 3 x + x = — 1 ⇔

x 1 + 2 x 2 — x 3 + 3 x 4 = 7 2 x 1 + 4 x 2 — 2 x 3 + 6 x 4 + ( — 2 ) ( x 1 + 2 x 2 — x 3 + 3 x 4 ) = 14 + ( — 2 ) × 7 x — x + 3 x + x + ( — 1 ) ( x 1 + 2 x 2 — x 3 + 3 x 4 ) = — 1 + ( — 1 ) × 7 ⇔

⇔ x 1 + 2 x 2 — x 3 + 3 x 4 = 7 0 = 0 — 3 x 2 + 4 x 3 — 2 x 4 = — 8

Из этого следует, что 2-ое уравнение можно смело удалять из системы и продолжать решение.

Если мы проводим прямой ход метода Гаусса, то одно или несколько уравнений может принять вид — некоторое число, которое отлично от нуля.

Это свидетельствует о том, что уравнение, обратившееся в равенство 0 = λ , не может обратиться в равенство ни при каких любых значениях переменных. Проще говоря, такая система несовместна (не имеет решения).

• В случае если при проведении прямого хода метода Гаусса одно или несколько уравнений принимают вид 0 = λ , где λ — некоторое число, которое отлично от нуля, то система несовместна.
• Если же в конце прямого хода метода Гаусса получается система, число уравнений которой совпадает с количеством неизвестных, то такая система совместна и определена: имеет единственное решение, которое вычисляется обратным ходом метода Гаусса.
• Если при завершении прямого хода метода Гаусса число уравнений в системе оказывается меньше количества неизвестных, то такая система совместна и имеет бесконечно количество решений, которые вычисляются при обратном ходе метода Гаусса.