Метод исключения метод гаусса: Решение систем линейных уравнений методом Гаусса

Содержание

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

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

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

Условно в методе Гаусса можно выделить 2 этапа: «прямой» и «обратный» ходы.

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

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

В основу метода Гаусса положены свойства равносильных (эквивалентных)

систем (т.е. имеющих одни и те же решения).

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

– перестановка уравнений местами;

– умножение всех членов уравнения на одно и то же число, отличное от нуля;

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

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

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

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

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

Алгоритм Метода Гаусса цикличен, т.е. одна и та же операция будет по очереди повторяться для каждой неизвестной. Условно его можно выразить фразой: «диагональный элемент не ноль, под ним нули».

Рассмотрим СЛАУ (случай ):

(6.1)

Пусть (еслито перестановкой уравнений местами добьемся, чтобы выполнялось условие. Это приведет к равносильной системе уравнений). Разделим 1-е уравнение системы на. Оно примет вид:

где

ШАГ 1. Умножая это уравнение последовательно на и прибавляя полученные уравнения в том же порядке ко 2-му, 3-му … -му уравнениям, исключим переменную из всех уравнений системы, начиная со второго.

Получим:

(6.2)

ШАГ 2. Пусть (если это не так, то перестановкой уравнений или неизвестных с изменением их номеров добьемся, чтобы выполнялось условие).

Разделим второе уравнение системы на . Это уравнение примет вид

где

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

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

(6.3)

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

Для любой совместной системы (6.1) числа в системе (6.3) равны нулю. В этом случае последниеуравнений являются тождествами и их можно исключить при решении системы (6.3). После исключения из системы (6.3) последнихуравнений возможны два случая: 1) число уравнений, оставшихся в системе (6.3), равно числу неизвестных, т.е. , тогда система (6.3) имеет треугольный вид и решение системы (6.1) единственное; 2)(тогда система (6.3) имеет ступенчатый вид и система (6.1) неопределенная, имеет бесчисленное множество решений).

Пример 1. Решить систему уравнений методом Гаусса:

Составим расширенную матрицу системы

Разделим первую строку матрицы на 2.

ШАГ 1.

ШАГ 2.

Разделим вторую строку полученной матрицы на

ШАГ 3.

Разделим третью строку на

Прямой ход на этом окончен.

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

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

из второго уравнения системы

из первого уравнения системы

Ответ:

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

Запишем и преобразуем расширенную матрицу системы

Уравнение, соответствующее третьей строке полученной матрицы, представляет равенство . Следовательно, система несовместна.

Ответ: решений нет.

Замечания:

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

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

  3. При решении СЛАУ методом Гаусса одновременно осуществляется исследование системы.

НОУ ИНТУИТ | Лекция | Умножение разреженных матриц

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

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

Прямые методы решения СЛАУ

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

n, является сильное влияние на окончательный результат округлений при вычислениях.

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

Например, в 80-х годах прошлого века точные методы применялись для решения систем до порядка 104, итерационные – до порядка 107, в 90-х – до порядков 10

5 и 108 соответственно. Современные суперкомпьютеры способны использовать точные методы при решении еще больших систем.

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

( 7. 1)

В матричном виде система может быть представлена как

( 7.2)

где есть вещественная матрица размера ; b и x – вектора из n элементов.

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

Метод исключения Гаусса

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

( 7.
3)

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

Метод Гаусса основывается на возможности выполнения преобразований линейных уравнений, которые не меняют при этом решение рассматриваемой системы (такие преобразования носят наименование эквивалентных). К числу таких преобразований относятся:

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

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

Последовательный алгоритм

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

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

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

( 7.4)

В итоге приходим к системе с верхней треугольной матрицей

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

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

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

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

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

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

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

Для выполнения обратного хода потребуется

Таким образом, общее время выполнения метода Гаусса при больших n можно оценить как

Параллельный алгоритм

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

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

При выполнении обратного хода метода Гаусса подзадачи выполняют необходимые вычисления для нахождения значения неизвестных. Как только какая-либо подзадача i, , определяет значение своей переменной , это значение должно быть использовано всеми подзадачам с номерами k, : подзадачи подставляют полученное значение новой неизвестной и выполняют корректировку значений для элементов вектора b.

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


Рис. 7.1. Ленточная схема

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

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

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

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

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

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

( 7.5)
Связь метода Гаусса и LU-разложения

( 7.6)

где L – нижняя треугольная матрица с диагональными элементами, равными единице, а U – верхняя треугольная матрица с ненулевыми диагональными элементами. LU-разложение также называют LU-факторизацией. Известно [4], что LU-разложение существует и единственно, если главные миноры матрицы A отличны от нуля.

Алгоритм LU-разложения тесно связан с методом исключения Гаусса. В самом деле, пусть мы решаем систему уравнений вида (7.2). Непосредственно проверяется, что преобразования k-го шага метода Гаусса равносильны домножению системы (7. 2) слева на матрицу

где – множители Гаусса из (7.4). Как было рассмотрено в п. 7.1.1, прямой ход метода Гаусса преобразует исходную систему уравнений к виду

с верхней треугольной матрицей U. Зная матрицы , можно записать матрицу U и вектор c как

Обозначим Можно непосредственно проверить, что

Отсюда получаем .

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

Рассмотренный нами алгоритм LU-факторизации реализован с помощью исключения по столбцу. Следует отметить, что можно сформулировать аналогичный алгоритм, основанный на исключении по строке. В самом деле, основная идея алгоритма с помощью исключения по столбцу заключается в том, что на i-й итерации ведущая строка с подходящими множителями вычитается из строк, лежащих ниже, чтобы занулить все элементы матрицы, расположенные в i-м столбце ниже диагонали. Между тем возможно и другое: на каждой i-й итерации можно вычитать из i-й строки все строки, расположенные выше, умноженные на подходящие коэффициенты, так, чтобы занулить все элементы i-й строки левее диагонали. При этом элементы матрицы L ниже главной диагонали и элементы матрицы U на главной диагонали и выше нее можно вычислять на месте матрицы А. Как и в случае исключения по столбцу, приведенная схема требует проведения операций

Рассмотрим теперь еще один способ LU-факторизаци, называемый компактной схемой. Пусть матрица допускает LU-разложение (7.6), где

т.е. при а при . Из соотношения (7.6) следует, что

Отсюда находим

Оценка числа операций данного алгоритма LUфакторизаци также составляет

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

( 7.7)

Обратный ход требует операций.

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

Страница не найдена — ПриМат

© 2012-2016: Нохум-Даниэль Блиндер (11), Анастасия Лозинская (10), Денис Стехун (8), Елизавета Савицкая (8), Игорь Любинский (8), Юлия Стерлянко (8), Александр Базан (7), Валентин Малявко (7), Анна Чалапчий (7), Константин Берков (7), Олег Шпинарев (7), Максим Швандт (6), Людмила Рыбальченко (6), Кирилл Волков (6), Татьяна Корнилова (6), Влад Радзивил (6), Елизавета Снежинская (5), Вадим Покровский (5), Даниил Радковский (5), Влад Недомовный (5), Александр Онищенко (5), Андрей Метасов (5), Денис Базанов (5), Александр Ковальский (5), Александр Земсков (5), Марина Чайковская (5), Екатерина Шибаева (5), Мария Корень (5), Анна Семененко (5), Мария Илларионова (5), Сергей Черкес (5), Алиса Ворохта (5), Валерия Заверюха (5), Никита Савко (4), Кондрат Воронов (4), Алина Зозуля (4), Иван Чеповский (4), Артем Рогулин (4), Игорь Чернега (4), Даниил Кубаренко (4), Ольга Денисова (4), Татьяна Осипенко (4), Яков Юсипенко (4), Ольга Слободянюк (4), Руслан Авсенин (4), Екатерина Фесенко (4), Дмитрий Заславский (4), Алина Малыхина (4), Андрей Лисовой (4), Полина Сорокина (4), Кирилл Демиденко (4), Дмитрий Стеценко (4), Александр Рапчинский (4), Святослав Волков (4), Иван Мясоедов (4), Владислав Стасюк (4), Алёна Гирняк (4), Николай Царев (4), Валентин Цушко (4), Павел Жуков (4), Роман Бронфен-Бова (4), Артём Романча (4), Анна Шохина (4), Иван Киреев (4), Виктор Булгаков (3), Дмитрий Мороз (3), Богдан Павлов (3), Игорь Вустянюк (3), Андрей Яроцкий (3), Лаура Казарян (3), Екатерина Мальчик (3), Анатолий Осецимский (3), Иван Дуков (3), Дмитрий Робакидзе (3), Вячеслав Зелинский (3), Данила Савчак (3), Дмитрий Воротов (3), Стефания Амамджян (3), Валерия Сиренко (3), Георгий Мартынюк (3), Виктор Иванов (3), Вячеслав Иванов (3), Валерия Ларикова (3), Евгений Радчин (3), Андрей Бойко (3), Милан Карагяур (3), Александр Димитриев (3), Иван Василевский (3), Руслан Масальский (3), Даниил Кулык (3), Стас Коциевский (3), Елизавета Севастьянова (3), Павел Бакалин (3), Антон Локтев (3), Андрей-Святозар Чернецкий (3), Николь Метри (3), Евелина Алексютенко (3), Константин Грешилов (3), Марина Кривошеева (3), Денис Куленюк (3), Константин Мысов (3), Мария Карьева (3), Константин Григорян (3), Колаев Демьян (3), Станислав Бондаренко (3), Ильдар Сабиров (3), Владимир Дроздин (3), Кирилл Сплошнов (3), Карина Миловская (3), Дмитрий Козачков (3), Мария Жаркая (3), Алёна Янишевская (3), Александра Рябова (3), Дмитрий Байков (3), Павел Загинайло (3), Томас Пасенченко (3), Виктория Крачилова (3), Таисия Ткачева (3), Владислав Бебик (3), Илья Бровко (3), Максим Носов (3), Филип Марченко (3), Катя Романцова (3), Илья Черноморец (3), Евгений Фищук (3), Анна Цивинская (3), Михаил Бутник (3), Станислав Чмиленко (3), Катя Писова (3), Дмитрий Дудник (3), Дарья Кваша (3), Игорь Стеблинский (3), Артем Чернобровкин (3), Яна Колчинская (2), Юрий Олейник (2), Кирилл Бондаренко (2), Елена Шихова (2), Татьяна Таран (2), Наталья Федина (2), Настя Кондратюк (2), Никита Гербали (2), Сергей Запорожченко (2), Николай Козиний (2), Георгий Луценко (2), Владислав Гринькив (2), Александр Дяченко (2), Анна Неделева (2), Никита Строгуш (2), Настя Панько (2), Кирилл Веремьев (2), Даниил Мозгунов (2), Андрей Зиновьев (2), Андрей Данилов (2), Даниил Крутоголов (2), Наталия Писаревская (2), Дэвид Ли (2), Александр Коломеец (2), Александра Филистович (2), Евгений Рудницкий (2), Олег Сторожев (2), Евгения Максимова (2), Алексей Пожиленков (2), Юрий Молоканов (2), Даниил Кадочников (2), Александр Колаев (2), Александр Гутовский (2), Павел Мацалышенко (2), Таня Спичак (2), Радомир Сиденко (2), Владислав Шиманский (2), Илья Балицкий (2), Алина Гончарова (2), Владислав Шеванов (2), Андрей Сидоренко (2), Александр Мога (2), Юлия Стоева (2), Александр Розин (2), Надежда Кибакова (2), Майк Евгеньев (2), Евгений Колодин (2), Денис Карташов (2), Александр Довгань (2), Нина Хоробрых (2), Роман Гайдей (2), Антон Джашимов (2), Никита Репнин (2), Инна Литвиненко (2), Яна Юрковская (2), Гасан Мурадов (2), Богдан Подгорный (2), Алексей Никифоров (2), Настя Филипчук (2), Гук Алина (2), Михаил Абабин (2), Дмитрий Калинин (2), Бриткариу Ирина (2), Никита Шпилевский (2), Алексей Белоченко (2), Юлиана Боурош (2), Никита Семерня (2),

%d0%bc%d0%b5%d1%82%d0%be%d0%b4%20%d0%b3%d0%b0%d1%83%d1%81%d1%81%d0%b0 — со всех языков на все языки

Все языкиАбхазскийАдыгейскийАфрикаансАйнский языкАканАлтайскийАрагонскийАрабскийАстурийскийАймараАзербайджанскийБашкирскийБагобоБелорусскийБолгарскийТибетскийБурятскийКаталанскийЧеченскийШорскийЧерокиШайенскогоКриЧешскийКрымскотатарскийЦерковнославянский (Старославянский)ЧувашскийВаллийскийДатскийНемецкийДолганскийГреческийАнглийскийЭсперантоИспанскийЭстонскийБаскскийЭвенкийскийПерсидскийФинскийФарерскийФранцузскийИрландскийГэльскийГуараниКлингонскийЭльзасскийИвритХиндиХорватскийВерхнелужицкийГаитянскийВенгерскийАрмянскийИндонезийскийИнупиакИнгушскийИсландскийИтальянскийЯпонскийГрузинскийКарачаевскийЧеркесскийКазахскийКхмерскийКорейскийКумыкскийКурдскийКомиКиргизскийЛатинскийЛюксембургскийСефардскийЛингалаЛитовскийЛатышскийМаньчжурскийМикенскийМокшанскийМаориМарийскийМакедонскийКомиМонгольскийМалайскийМайяЭрзянскийНидерландскийНорвежскийНауатльОрокскийНогайскийОсетинскийОсманскийПенджабскийПалиПольскийПапьяментоДревнерусский языкПортугальскийКечуаКвеньяРумынский, МолдавскийАрумынскийРусскийСанскритСеверносаамскийЯкутскийСловацкийСловенскийАлбанскийСербскийШведскийСуахилиШумерскийСилезскийТофаларскийТаджикскийТайскийТуркменскийТагальскийТурецкийТатарскийТувинскийТвиУдмурдскийУйгурскийУкраинскийУрдуУрумскийУзбекскийВьетнамскийВепсскийВарайскийЮпийскийИдишЙорубаКитайский

 

Все языкиАбхазскийАдыгейскийАфрикаансАйнский языкАлтайскийАрабскийАварскийАймараАзербайджанскийБашкирскийБелорусскийБолгарскийКаталанскийЧеченскийЧаморроШорскийЧерокиЧешскийКрымскотатарскийЦерковнославянский (Старославянский)ЧувашскийДатскийНемецкийГреческийАнглийскийЭсперантоИспанскийЭстонскийБаскскийЭвенкийскийПерсидскийФинскийФарерскийФранцузскийИрландскийГалисийскийКлингонскийЭльзасскийИвритХиндиХорватскийГаитянскийВенгерскийАрмянскийИндонезийскийИнгушскийИсландскийИтальянскийИжорскийЯпонскийЛожбанГрузинскийКарачаевскийКазахскийКхмерскийКорейскийКумыкскийКурдскийЛатинскийЛингалаЛитовскийЛатышскийМокшанскийМаориМарийскийМакедонскийМонгольскийМалайскийМальтийскийМайяЭрзянскийНидерландскийНорвежскийОсетинскийПенджабскийПалиПольскийПапьяментоДревнерусский языкПуштуПортугальскийКечуаКвеньяРумынский, МолдавскийРусскийЯкутскийСловацкийСловенскийАлбанскийСербскийШведскийСуахилиТамильскийТаджикскийТайскийТуркменскийТагальскийТурецкийТатарскийУдмурдскийУйгурскийУкраинскийУрдуУрумскийУзбекскийВодскийВьетнамскийВепсскийИдишЙорубаКитайский

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

СОДЕРЖАНИЕ Введение 1 Постановка задачи 2 Математические и алгоритмические основы решения задачи 2. 1 Схема единственного деления 2.1.1 Прямой ход 2.1.2 Обратный ход 2.2 Метод Гаусса с выбором главного элемента по столбцу 3 Функциональные модели и блок-схемы решения задачи 4 Программная реализация решения задачи 5 Пример выполнения программы Заключение Список использованных источников и литературы ВВЕДЕНИЕ Решение систем линейных алгебраических уравнений – одна из основных задач вычислительной линейной алгебры. Хотя задача решения системы линейных уравнений сравнительно редко представляет самостоятельный интерес для приложений, от умения эффективно решать такие системы часто зависит сама возможность математического моделирования самых разнообразных процессов с применением ЭВМ. Значительная часть численных методов решения различных (в особенности – нелинейных) задач включает в себя решение систем линейных уравнений как элементарный шаг соответствующего алгоритма. Одна из трудностей практического решения систем большой размерности связанна с ограниченностью оперативной памяти ЭВМ. Хотя объем оперативной памяти вновь создаваемых вычислительных машин растет очень быстро, тем не менее, еще быстрее возрастают потребности практики в решении задач все большей размерности. В значительной степени ограничения на размерность решаемых систем можно снять, если использовать для хранения матрицы внешние запоминающие устройства. Однако в этом случае многократно возрастают как затраты машинного времени, так и сложность соответствующих алгоритмов. Поэтому при создании вычислительных алгоритмов линейной алгебры большое внимание уделяют способам компактного размещения элементов матриц в памяти ЭВМ. К счастью, приложения очень часто приводят к матрицам, в которых число ненулевых элементов много меньше общего числа элементов матрицы. Такие матрицы принято называть разреженными. Одним из основных источников разреженных матриц являются математические модели технических устройств, состоящих из большого числа элементов, связи между которыми локальны. Простейшие примеры таких устройств – сложные строительные конструкции и большие электрические цепи. Пример 1. Решить следующую систему с помощью метода исключения Гаусса с выбором главного элемента по столбцу: . Решение: . Пример 2. Решить следующую систему с помощью метода исключения Гаусса с выбором главного элемента по столбцу: . Составим расширенную матрицу системы. . Решением системы являются:x =1, y = 2, z = 3. 2 Математические и алгоритмические основы решения задачи 2.1 Схема единственного деления Рассмотрим сначала простейший вариант метода Гаусса, называемый схемой единственного деления. 2.1.1 Прямой ход Прямой ход состоит из n – 1 шагов исключения. 1-й шаг. Целью этого шага является исключение неизвестного x1 из уравнений с номерами i = 2, 3, …, n. Предположим, что коэффициент a11 = 0. Будем называть его главным элементом 1-го шага. Найдем величины qi1 = ai1/a11 (i = 2, 3, …, n), называемые множителями 1-го шага. Вычтем последовательно из второго, третьего, n-го уравнений системы первое уравнение, умноженное соответственно на q21, q31, qn1. Это позволит обратить в нуль коэффициенты при x1 во всех уравнениях, кроме первого. В результате получим эквивалентную систему a11x1 + a12x2 + a13x3 + … + a1nxn = b1 , a22(1)x2 + a23(1)x3 + … + a2n(1)xn = b2(1) , a32(1)x2 + a33(1)x3 + … + a3n(1)xn = b3(1) , an2(1)x2 + an3(1)x3 + … + ann(1)xn = bn(1) . в которой aij(1) и bij(1) вычисляются по формулам aij(1) = aij − qi1a1j bi(1) = bi − qi1b1. 2-й шаг. Целью этого шага является исключение неизвестного x2 из уравнений с номерами i = 3, 4, …, n. Пусть a22(1) ≠ 0, где a22(1) – коэффициент, называемый главным (или ведущим) элементом 2-го шага. Вычислим множители 2-го шага qi2 = ai2(1) / a22(1) (i = 3, 4, …, n) и вычтем последовательно из третьего, четвертого, …, n-го уравнения системы второе уравнение, умноженное соответственно на q32, q42, …, qm2. В результате получим систему a11x1 + a12x2 + a13x3 + a1nxn =b1, a22(1)x2 + a23(1)x3 + a2n(1) =b2(1) , a33(2)x3 + a3n(2)xn =b3(2), an3(2)x3 + ann(2)xn = bn(2) Здесь коэффициенты aij(2) и bij(2) вычисляются по формулам aij(2) = aij(1) – qi2a2j(1) ,bi(2) = bi(1) – qi2b2(1). Аналогично проводятся остальные шаги. Опишем очередной k-й шаг. k-й шаг. В предположении, что главный (ведущий) элемент k-го шага akk(k–1) отличен от нуля, вычислим множители k-го шага qik = aik(k–1) / akk(k–1) (i = k + 1, …, n) и вычтем последовательно из (k + 1)-го, …, n-го уравнений полученной на предыдущем шаге системы k-e уравнение, умноженное соответственно на qk+1,k, qk+2,k, …, qnk. 3 Функциональные модели и блок-схемы решения задачи Блок-схема решения задачи представлена на рисунке 1. Условные обозначения: • K – размерность матрицы; • MATRIX – матрица; • N – размерность матрицы; • X – матрица решения СЛАУ; • I_MAX – индекс максимального элемента в строке; • J_MAX – индекс максимального элемента в столбце; • OTV – массив позиций элементов; • RES – вспомогательный массив; • TEMP – временная переменная; • GLAV_EL – функция, определяющая на какой позиции должен стоять главный элемент; • INDEX – рабочая переменная. Рисунок 1 – Блок-схема решения задачи для функции GAUSS \ 4 Программная реализация решения задачи ФУНКЦИЯ ПОИСКА МАКСИМАЛЬНОГО ЭЛЕМЕНТА И ПЕРЕСТАНОВКИ СТРОК И СТОЛБЦОВ (DEFUN GLAV_EL (K MATRIX N X) (DECLARE (SPECIAL I_MAX)) (DECLARE (SPECIAL J_MAX)) (DECLARE (SPECIAL TEMP)) (DECLARE (SPECIAL I)) (SETQ I_MAX K) (SETQ J_MAX K) ;ИЩЕМ МАКСИМАЛЬНЫЙ ПО МОДУЛЮ ЭЛЕМЕНТ (DO ((I K)) ((>= I N)) (DO ((J K)) ((>= J N)) (IF (< (ABS (AREF MATRIX I_MAX J_MAX)) (ABS (AREF MATRIX I J))) (PROGN (SETQ I_MAX I) (SETQ J_MAX J) ) ) (SETQ J (+ J 1)) ) ((J N)) ((< J K)) (SETF (AREF MATRIX K J) (FLOAT (/ (AREF MATRIX K J) (AREF MATRIX K K)))) (SETQ J (- J 1)) ) (DO ((I (+ K 1))) ((>= I N)) (DO ((J N)) ((< J K)) (SETF (AREF MATRIX I J) (- (AREF MATRIX I J) (* (AREF MATRIX K J) (AREF MATRIX I K)))) (SETQ J (- J 1)) ) (SETQ I (+ I 1)) ) (SETQ K (+ K 1)) ) ;ОБРАТНЫЙ КОД (DO ((I 0)) ((>= I N)) (SETF (AREF X I) (AREF MATRIX I N)) (SETQ I (+ I 1)) ) (DO ((I (- N 2))) ((< I 0)) (DO ((J (+ I 1))) ((>= J N)) (SETF (AREF X I) (- (AREF X I) (* (AREF X J) (AREF MATRIX I J)))) (SETQ J (+ J 1)) ) (SETQ I (- I 1)) ) (DO ((I 0) (INDEX 0)) ((>= I N) RES) (DO ((J 0)) ((>= J N)) ;РАССТАВЛЯЕМ КОРНИ ПО ПОРЯДКУ (IF (= I (AREF OTV J)) (PROGN (SETF (AREF RES INDEX) (AREF X J)) (SETQ INDEX (+ INDEX 1)) ) ) (SETQ J (+ J 1)) ) (SETQ I (+ I 1)) ) (SETQ X RES) ) (SETQINPUT_STREAM(OPEN ” D: \GAUSS_MATRIX. TXT” :DIRECTION :INPUT)) ;ПОЛУЧАЕМ РАЗМЕРНОСТЬ МАТРИЦЫ (SETF N (READINPUT_STREAM)) ;ПОЛУЧАЕМ МАТРИЦУ (SETF MATRIX (READINPUT_STREAM)) (CLOSEINPUT_STREAM) (SETQ X (MAKE-ARRAY 50 :ELEMENT-TYPE ‘INTEGER :INITIAL- ELEMENT 0)) (SETQ RES (GAUSS MATRIX N X)) ;ЗАПИСЫВАЕМ КОРНИ СЛАУ В ФАЙЛ (SETQOUTPUT_STREAM(OPEN ” D: \KORNI_SLAY.TXT” :DIRECTION :OUTPUT)) (PRINT RES OUTPUT_STREAM) (TERPRIOUTPUT_STREAM) (CLOSEOUTPUT_STREAM) ЗАКЛЮЧЕНИЕ Проблема повышения качества вычислений, как несоответствие между желаемым и действительным, существует и будет существовать в дальнейшем. Ее решению будет содействовать развитие информационных технологий, которое заключается как в совершенствовании методов организации информационных процессов, так и их реализации с помощью конкретных инструментов – сред и языков программирования. Итогом работы можно считать созданную функциональную модель численного решения системы линейных уравнений с помощью метода исключения Гаусса с выбором главного элемента по столбцу. Созданная функциональная модель и ее программная реализация могут служить органической частью решения более сложных задач. СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ и литературы 1. Бронштейн, И.Н. Справочник по математике для инженеров и учащихся втузов [Текст] / И.Н. Бронштейн, К.А. Семендяев. – М.: Наука, 2007. – 708 с. 2. Васильев, Ф.П. Численные методы решения экстремальных задач. [Текст] / Ф.П. Васильев – М.: Наука, 2002. C. 415. 3. Высшая документация – Online документация [Электронный ресурс] – Режим доступа: http://vm.psati.ru/online-vmath/index.php?page=8 4. Калиткин, Н.Н. Численные методы. [Электронный ресурс] / Н.Н. Калиткин. – М.: Питер, 2001. С. 504. 5. Кнут, Д.Э. Искусство программирования. Основные алгоритмы [Текст] / Д.Э. Кнут. – М.: Вильямс, 2007. Т.1.– 712 с. 6. Метод Гаусса [Электронный ресурс] – Режим доступа: http:// www.wikipedia.org/wiki/Метод_Гаусса. 7. Симанков, В.С. Основы функционального программирования [Текст] / В.С. Симанков, Т.Т. Зангиев, И.В. Зайцев. – Краснодар: КубГТУ, 2002. – 160 с. 8. Степанов, П.А. Функциональное программирование на языке Lisp. [Электронный ресурс] / П.А.Степанов, А. В. Бржезовский. – М.: ГУАП, 2003. С. 79. 9. Хювенен Э. Мир Лиспа [Текст] / Э. Хювенен, Й. Сеппянен. – М.: Мир, 1990. – 460 с.

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

Решить систему уравнений: .

Записав расширенную матрицу системы, преобразуем ее с помощью преобразований не изменяющих ранг матрицы. Цель: в первом столбце все элементы, кроме одного, должны стать равными нулю. Это равносильно тому, что из 2го, 3го и 4го уравнений будет исключена неизвестная Х1. Для достижения цели первую строку, умноженную на 2, –3 и –1 прибавим, соответственно, к 2ой, 3ей и 4ой строке. Получим:

~.

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

Далее вторую строку, умноженную на –1 прибавим к 4ой строке, тем самым исключив Х2 из третьего и четвертого уравнений и, наконец исключим Х3 из 4го уравнения, прибавив третью строку, умноженную на –1 к четвертой:

~ ~ .

Имеем rangA = Rangà = 3. Система совместна. N R = 5 –3 = 2, dimL = dimM = 2. Так как, размерность пространства решений однородной системы равна 2, то в системе имеется две свободных неизвестных. Выберем в качестве свободных переменных Х3, Х4. Отделим в матрице свободные неизвестные вертикальной пунктирной линией: .

Положив Х4 = 1, Х5 = 1, получим Х1 = Х2 = х3 = 1. Т. е. частное решение неоднородной системы (1, 1, 1, 1, 1).

Далее рассмотрим однородную систему уравнений с матрицей . Тогда

.

Положив Х4 = 1, Х5 = 0 Þ Е1(2, 2, –6, 1, 0). Положив Х4 = 0, Х5 = 1 Þ Е2(2, 2, –7, 0, 1), (Е1, Е2 – ба­зис пространства решений). Отсюда Х = (1,1,1,1,1) + a(2,2,–6,1,0)+ b(2,2,–7,0,1), где a, b – любые.

Если положить Х4 = Х5 = 0, то получим Х3 = 14, Х2 = –3, Х1 = –3, т. е. (–3, –3, 14, 0, 0) еще одно частное решение данной системы. Следовательно, общее решение исходной системы можно записать и в таком виде: Х = (–3, –3, 14, 0, 0) + a(2, 2, –6, 1, 0) + b(2, 2, –7, 0, 1), где a, b – любые.

Нужно обратить внимание и на то, что разность двух частных решений неоднородной системы (–3, –3, 14, 0, 0) – (1, 1, 1, 1, 1) есть решение соответствующей однородной системы уравнений.

< Предыдущая   Следующая >

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

  1. Система линейных алгебраических уравнений

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

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

где числа aij называются коэффициентами системы, числа bi – свободными членами, aij и bi (i=1,…, m; b=1,…, n) представляют собой некоторые известные числа, а x1,…, xn – неизвестные. В обозначении коэффициентов aij первый индекс i обозначает номер уравнения, а второй j – номер неизвестного, при котором стоит этот коэффициент. Подлежат нахождению числа xn. Такую систему удобно записывать в компактной матричной форме: AX=B. Здесь А – матрица коэффициентов системы, называемая основной матрицей;

– вектор-столбец из неизвестных xj.

– вектор-столбец из свободных членов bi.

Произведение матриц А*Х определено, так как в матрице А столбцов столько же, сколько строк в матрице Х (n штук).

Расширенной матрицей системы называется матрица A системы, дополненная столбцом свободных членов

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

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

Решением системы называется n значений неизвестных х1=c1, x2=c2,…, xn=cn, при подстановке которых все уравнения системы обращаются в верные равенства. Всякое решение системы можно записать в виде матрицы-столбца

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

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

Решить систему – это значит выяснить, совместна она или несовместна. Если система совместна, найти ее общее решение.

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

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

Система линейных уравнений называется однородной, если все свободные члены равны нулю:

Однородная система всегда совместна, так как x1=x2=x3=…=xn=0 является решением системы. Это решение называется нулевым или тривиальным.

  1. Метод исключения Гаусса

2.1 Сущность метода исключения Гаусса

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

Процесс решения по методу Гаусса состоит из двух этапов: прямой и обратный ходы.

  1. Прямой ход.

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

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

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

Приведенная ниже система имеет ступенчатый вид:

,

где

Коэффициенты aii называются главными (ведущими) элементами системы.

1-й шаг.

Будем считать, что элемент  (если a11=0, переставим строки матрицы так, чтобы a11 не был равен 0. Это всегда возможно, т. к. в противном случае матрица содержит нулевой столбец, ее определитель равен нулю и система несовместна).

Преобразуем систему, исключив неизвестное х1 во всех уравнениях, кроме первого (используя элементарные преобразования системы). Для этого умножим обе части первого уравнения на  и сложим почленно со вторым уравнением системы (или из второго уравнения почленно вычтем первое, умноженное на ). Затем умножим обе части первого уравнения на  и сложим с третьим уравнением системы (или из третьего почленно вычтем первое, помноженное на ). Таким образом, последовательно умножаем первую строку на число и прибавляем к i-й строке, для i=2, 3, …, n.

Продолжая этот процесс, получим эквивалентную систему:

Здесь  – новые значения коэффициентов при неизвестных и свободные члены в последних m-1 уравнениях системы, которые определяются формулами:

Таким образом, на первом шаге уничтожаются все коэффициенты, лежащие под первым ведущим элементом a110, на втором шаге уничтожаются элементы, лежащие под вторым ведущим элементом а22(1) (если a22(1)0) и т.д. Продолжая этот процесс и дальше, мы, наконец, на (m-1) шаге приведем исходную систему к треугольной системе.

Если в процессе приведения системы к ступенчатому виду появятся нулевые уравнения, т.е. равенства вида 0=0, их отбрасывают. Если же появится уравнение вида  то это свидетельствует о несовместности системы.

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

  1. Обратный ход.

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

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

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

Примечание: на практике удобнее работать не с системой, а с расширенной ее матрицей, выполняя все элементарные преобразования над ее строками. Удобно, чтобы коэффициент a11 был равен 1 (уравнения переставить местами, либо разделить обе части уравнения на a11).

Гаусс Джордан Устранение – Объяснение и примеры

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

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

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

Что такое метод исключения Гаусса?

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

  • для представления системы линейных уравнений в форме расширенной матрицы
  • затем выполнение над ней строковых операций $ 3 до тех пор, пока не будет получена сокращенная форма эшелона строк (RREF) достигнуто
  • Наконец, мы можем легко распознать решения из RREF

Давайте посмотрим, что такое расширенная матричная форма, операции со строками стоимостью 3 $, которые мы можем выполнять с матрицей, и упрощенная форма эшелона строк матрицы.

Расширенная матрица

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

$ \ begin {align *} 2x + 3y & = \, 7 \\ x – y & = 4 \ end {align *} $

We запишет расширенную матрицу этой системы, используя коэффициенты уравнений и запишет ее в стиле , показанном ниже:

$ \ left [\ begin {array} {rr | r} 2 & 3 & 7 \\ 1 & -1 & 4 \ end {array} \ right] $

Пример использования одновременных уравнений $ 3 $ показан ниже:

$ \ begin {align *} 2x + y + z & = \, 10 \\ x + 2y + 3z & = 1 \\ – x – y – z & = 2 \ end {align *} $

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

$ \ left [\ begin {array} {rrr | r} 2 & 1 & 1 & 10 \\ 1 & 2 & 3 & 1 \\ – 1 & – 1 & – 1 & 2 \ end {array} \ right] $

Операции со строками в матрице

Есть $ 3 $ элементарных операций со строками , которые мы можем выполнять с матрицами.Это не изменит решения системы. Это:

  1. Обмен $ 2 $ строк
  2. Умножить строку на ненулевой ($ \ neq 0 $) скаляр
  3. Добавить или вычесть скалярное кратное одной строки из другой строки.

Уменьшенная форма эшелона строк

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

  1. Строки с нулевыми записями (все элементы этой строки равны s) находятся внизу матрицы.
  2. Начальная запись (первая ненулевая запись в строке) каждой ненулевой строки соответствует справа ведущей записи строки непосредственно над ней.
  3. Начальная запись в любой ненулевой строке – 1 доллар.
  4. Все записи в столбце, содержащем начальную запись ($ 1 $), нулевые.

Как выполнить исключение Гаусса Джордана

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

  1. Поменяйте местами строки так, чтобы все строки с нулевыми записями находились внизу матрицы.
  2. Поменяйте местами строки так, чтобы строка с самой большой левой цифрой находилась наверху матрицы.
  3. Умножьте верхнюю строку на скаляр, который преобразует ведущую запись верхней строки в $ 1 $ (если ведущей записью верхней строки является $ a $, умножьте ее на $ \ frac {1} {a} $, чтобы получить $ 1 $).
  4. Сложите или вычтите числа, кратные верхней строке, из других строк, чтобы все записи в столбце ведущей записи верхней строки были нулями.
  5. Выполните шаги $ 2 – 4 $ для следующей крайней левой ненулевой записи , пока все ведущие записи каждой строки не будут равны 1 $.
  6. Поменяйте местами строки так, чтобы первая запись каждой ненулевой строки находилась справа от ведущей записи строки непосредственно над ней

На первый взгляд, запомнить / запомнить шаги не так просто. Это вопрос решения нескольких проблем, пока вы не освоитесь с процессом. Существует также фактор , интуиция , которая играет B-I-G роль в выполнении исключения Гаусса Джордана.

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

Пример 1

Решите систему, показанную ниже, используя метод исключения Гаусса Джордана:

$ \ begin {align *} {- x} + 2y & = \, {- 6} \\ { 3x} – 4y & = {14} \ end {align *} $

Решение

Первый шаг – написать расширенную матрицу системы.Мы показываем это ниже:

$ \ left [\ begin {array} {r r | r} – 1 & 2 & – 6 \\ 3 & -4 & 14 \ end {array} \ right] $

Теперь наша задача – преобразовать матрицу в сокращенную форму эшелона строк (RREF), выполнив $ 3 $ элементарные операции со строками.

У нас есть расширенная матрица:

$ \ left [\ begin {array} {r r | r} – 1 & 2 & – 6 \\ 3 & – 4 & 14 \ end {array} \ right] $

Шаг 1:

Мы можем умножить первую строку на $ – 1 $, чтобы получить ведущий вход $ 1 $.Показано ниже:

$ \ left [\ begin {array} {r r | r} 1 & – 2 & 6 \\ 3 & – 4 & 14 \ end {array} \ right] $

Шаг 2:

Теперь мы можем умножить первую строку на 3 $ и вычесть ее из второй ряд. Показано ниже:

$ \ left [\ begin {array} {r r | r} 1 & -2 & 6 \\ {3 – (1 \ times 3)} & {-4 – (-2 \ times 3)} & {14 – (6 \ times 3)} \ end {array} \ справа] $

$ = \ left [\ begin {array} {rr | r} 1 & – 2 & 6 \\ 0 & 2 & – 4 \ end {array} \ right] $

У нас есть $ 0 $ как первая запись второй строки.

Шаг 3:

Чтобы сделать вторую запись второй строки $ 1 $, мы можем умножить вторую строку на $ \ frac {1} {2} $. Показано ниже:

$ \ left [\ begin {array} {r r | r} 1 & – 2 & 6 \\ {\ frac {1} {2} \ times 0} & {\ frac {1} {2} \ times 2} & {\ frac {1} {2} \ times – 4} \ end {array} \ right] $

$ = \ left [\ begin {array} {rr | r} 1 & – 2 & 6 \\ 0 & 1 & – 2 \ end {array} \ right] $

Шаг 4:

Мы почти у цели!

Вторая запись первой строки должна быть $ 0 $.Для этого мы умножаем вторую строку на $ 2 $ и добавляем ее к первой строке. Показано ниже:

$ \ left [\ begin {array} {r r | r} {1 + (0 \ times 2)} & {- 2 + (1 \ times 2)} & {6 + (- 2 \ times 2)} \\ 0 & 1 & – 2 \ end {array} \ справа] $

$ = \ left [\ begin {array} {rr | r} 1 & 0 & 2 \\ 0 & 1 & – 2 \ end {array} \ right] $

Это сокращенный эшелон строк формы . Из расширенной матрицы мы можем написать два уравнения (решения):

$ \ begin {align *} x + 0y & = \, 2 \\ 0x + y & = -2 \ end {align *} $

$ \ begin {align *} x & = \, 2 \\ y & = – 2 \ end {align *} $

Таким образом, решение системы уравнений: $ x = 2 $ и $ y = – 2 $.

Пример 2

Решите систему, показанную ниже, используя метод исключения Гаусса Джордана:

$ \ begin {align *} x + 2y & = \, 4 \\ x – 2y & = 6 \ end { align *} $


Решение

Запишем расширенную матрицу системы уравнений:

$ \ left [\ begin {array} {rr | r} 1 & 2 & 4 \\ 1 & – 2 & 6 \ end {array} \ right] $

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

Шаг 1:

Умножаем первую строку на $ 1 $, а затем вычитаем ее из второй строки. По сути это вычитание первой строки из второй:

$ \ left [\ begin {array} {r r | r} 1 & 2 & 4 \\ 1 – 1 & – 2 – 2 & 6 – 4 \ end {array} \ right] $

$ = \ left [\ begin {array} {r r | r} 1 & 2 & 4 \\ 0 & – 4 & 2 \ end {array} \ right] $

Шаг 2:

Мы умножаем вторую строку на $ – \ frac {1} {4} $, чтобы получить вторая запись строки, $ 1 $:

$ \ left [\ begin {array} {rr | r} 1 и 2 и 4 \\ 0 \ times – \ frac {1} {4} & – 4 \ times – \ frac {1} {4} и 2 \ times – \ frac {1} {4} \ end {массив} \ right] $

$ = \ left [\ begin {array} {rr | r} 1 & 2 & 4 \\ 0 & 1 & – \ frac {1} {2} \ end {array} \ right] $

Шаг 3:

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

$ \ left [\ begin {array} {rr | r} 1 + (- 2 \ times 0) & 2+ (- 2 \ times 1) & 4 + (- 2 \ times – \ frac {1} {2}) \\ 0 & 1 & – \ frac {1 } {2} \ end {array} \ right] $

$ = \ left [\ begin {array} {rr | r} 1 & 0 & 5 \\ 0 & 1 & – \ frac {1} {2} \ end {array} \ right] $

Это сокращенный ряд строк , , форма .Из расширенной матрицы мы можем написать два уравнения (решения):

$ \ begin {align *} x + 0y & = \, 5 \\ 0x + y & = – \ frac {1} {2} \ end {align *} $

$ \ begin {align *} x & = \, 5 \\ y & = – \ frac {1} {2} \ end {align *} $

Таким образом, решение системы уравнений составляет $ x = 5 $ и $ y = – \ frac {1} {2} $.

Практические вопросы
  1. Решите систему, показанную ниже, используя метод исключения Гаусса Джордана:

    $ \ begin {align *} 2x + y & = \, – 3 \\ – x – y & = 2 \ end {align *} $

  2. Решите систему, показанную ниже, используя метод исключения Гаусса Джордана:

    $ \ begin {align *} x + 5y & = \, 15 \\ – x + 5y & = 25 \ end {align *} $

Ответы

  1. Начнем с написания расширенной матрицы системы уравнений:

    $ \ left [\ begin {array} {rr | r} 2 & 1 & – 3 \\ – 1 & – 1 & 2 \ end {array} \ right] $

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

    Первый,
    Меняем знаки второй строки местами. Итак, имеем:
    $ \ left [\ begin {array} {r r | r} 1 & 1 & – 2 \\ 2 & 1 & – 3 \ end {array} \ right] $
    Во-вторых,
    Мы дважды вычитаем первую строку из второй строки:
    $ \ left [\ begin {array} { rr | r} 1 & 1 & – 2 \\ 2 – (2 \ times 1) & 1 – (2 \ times 1) & – 3 – (2 \ times – 2) \ end {array} \ right] $
    $ = \ left [\ begin {array} {rr | r} 1 & 1 & – 2 \\ 0 & – 1 & 1 \ end {array} \ right] $
    В-третьих,
    Мы инвертируем вторую строку, чтобы получить:
    $ = \ left [\ begin {array} {rr | r} 1 & 1 & – 2 \\ 0 & 1 & – 1 \ end {array} \ right] $
    Наконец,
    Мы вычитаем вторую строку из первой и получаем:
    $ = \ left [\ begin { массив} {rr | r} 1 & 0 & – 1 \\ 0 & 1 & – 1 \ end {array} \ right] $

    Из этой расширенной матрицы мы можем написать два уравнения (решения):

    $ \ begin {align *} x + 0y & = \, – 1 \\ 0x + y & = – 1 \ end {align *} $

    $ \ begin {align *} x & = \, – 1 \\ y & = – 1 \ end {align *} $

    Таким образом, решение системы уравнений: $ x = – 1 $ и $ y = – 1 $.

  2. Расширенная матрица системы:
    $ \ left [\ begin {array} {rr | r} 1 & 5 & 15 \\ – 1 & 5 & 25 \ end {array} \ right] $
    Давайте приведите эту матрицу к приведенной форме эшелона строк и найдите решение системы.

    Сначала
    Отмените первую строку, затем вычтите ее из второй строки, чтобы получить:
    $ \ left [\ begin {array} {rr | r} 1 & 5 & 15 \\ – 1 – (- 1) & 5 – (- 5) & 25 – (- 15) \ end {array} \ right] $
    $ = \ left [\ begin {array} {rr | r} 1 & 5 & 15 \\ 0 & 10 & 40 \ end {array} \ right] $
    Во-вторых,
    Разделите вторую строку на $ 10 $, чтобы получить:
    $ \ left [\ begin {array} {rr | r} 1 & 5 & 15 \\ 0 & 1 & 4 \ end {array} \ right] $
    Затем
    Умножьте вторую строку на $ 5 $ и вычтите ее из первой строки, чтобы получить окончательное решение:
    $ \ left [\ begin {array} {rr | r} 1 – (5 \ times 0) & 5 – (5 \ times 1) & 15 – (5 \ times 4) \\ 0 & 1 & 4 \ end {array} \ right] $
    $ = \ left [ \ begin {array} {rr | r} 1 & 0 & – 5 \\ 0 & 1 & 4 \ end {array} \ right] $
    Это сокращенная форма эшелона строк (RREF).Из этой расширенной матрицы мы можем написать два уравнения (решения):

    $ \ begin {align *} x & = \, – 5 \\ y & = 4 \ end {align *} $

    Таким образом, решение системы уравнений $ x = – 5 $ и $ y = 4 $.

Предыдущий урок | Главная страница | Следующий урок

Метод исключения Гаусса


Далее: Строка уменьшенная форма эшелона Up: операции со строками и аналог Предыдущая: Операции со строками и аналог Содержание D EFINITION 2.2.10 (Метод прямого / исключения Гаусса) Исключение Гаусса – это метод решения линейной системы (состоящий из уравнения в неизвестные) за счет приведения дополненной матрицы в верхнетреугольную форму Этот процесс исключения также называется методом прямого исключения.

Следующие примеры иллюстрируют процедуру исключения Гаусса.

E XAMPLE 2.2,11 Решите линейную систему по Гауссу метод устранения.

Решение: В этом случае расширенная матрица Метод продолжается по следующие шаги.
  1. Развязка а также уравнение (или ).
  2. Разделите уравнение (или же ).
  3. Добавить раз уравнение уравнение (или же ).
  4. Добавить раз уравнение уравнение (или ).
  5. Умножить уравнение (или же ).

Последнее уравнение дает второе уравнение теперь дает Наконец, первое уравнение дает Следовательно, множество решения УНИКАЛЬНЫЙ РЕШЕНИЕ .

E XAMPLE 2.2.12 Решите линейную систему по Гауссу метод устранения.

Решение: В этом случае расширенная матрица и метод работает следующим образом:
  1. Добавить умножить первое уравнение на второе уравнение.
  2. Добавить умножить первое уравнение на третье уравнение.
  3. Добавить умножить второе уравнение на третье уравнение
Таким образом, множество решений есть с участием произвольный. Другими словами, в системе БЕСКОНЕЧНЫХ НОМЕРА. РЕШЕНИЙ . E XAMPLE 2.2.13 Решите линейную систему по Гауссу метод устранения.

Решение: В этом случае расширенная матрица и метод работает следующим образом:
  1. Добавить умножить первое уравнение на второе уравнение.
  2. Добавить умножить первое уравнение на третье уравнение.
  3. Добавить умножить второе уравнение на третье уравнение
Третье уравнение на последнем шаге: Это никогда не может быть справедливым для любого значения Следовательно В системе НЕТ РЕШЕНИЯ . Замечание 2.2.14 Обратите внимание, что для решения линейной системы нужно применять только элементарные строковые операции с расширенной матрицей

Далее: Строка уменьшенная форма эшелона Up: операции со строками и аналог Предыдущая: Операции со строками и аналог Содержание
А К Лал 2007-09-12

Метод исключения Гаусса – обзор

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

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

Комплексная матрица n × n W является невырожденной тогда и только тогда | W | ≠ 0, если ранг ( W ) = n .

Если W , Z являются комплексными матрицами n × n , то | WZ | = | Вт || Z |, | W T | = | W | и | W * | = | W¯ | = | W | ¯.

Если A является комплексной матрицей n × n , то λ∈C является собственным значением для A тогда и только тогда, когда существует ненулевой вектор v∈Cn такой, что Av = λ v . Такой ненулевой комплексный вектор v является собственным вектором для A , связанного с λ .

Если A представляет собой комплексную матрицу n × n , собственные значения A являются комплексными корнями характеристического полинома pA (x) = xIn − A из A , который делится на комплексные числа на n линейных множителей.То есть сумма алгебраических кратностей собственных значений A равна n .

Комплексная матрица является диагонализуемой тогда и только тогда, когда существует невырожденная комплексная матрица P такая, что P −1 AP = D является диагональной матрицей. Метод диагонализации применяется к комплексным матрицам.

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

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

Метод исключения Гаусса

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

Имеем систему: $$$ \ left \ {\ begin {array} {c} 3x + 2y + z = 1 \\ 5x + 3y + 4z = 2 \ x + y-z = 1 \ end {array} \ right. $$$

Первый шаг – написание системы в матричной форме. Посмотрите, что в матрице мы берем коэффициенты и постоянные члены. $$$ \ begin {pmatrix} 3 & 2 & 1 & | 1 \\ 5 & 3 & 4 & | 2 \\ 1 & 1 & -1 & | 1 \ end {pmatrix} $$$

Используя уже известные правила, мы должны получить систему эшелонов, которая будет выглядеть следующим образом: $$$ \ begin {pmatrix} a_ {11} & a_ {12} & a_ {13} & | b_1 \\ \ fbox {} & a_ {22} & a_ {23} & | b_2 \\ \ fbox {} & \ fbox {} & a_ {33} & | b_3 \ end {pmatrix} $$$ Давай найдем это $$$ \ begin {pmatrix} 3 & 2 & 1 & | 1 \\ 5 & 3 & 4 & | 2 \\ 1 & 1 & -1 & | 1 \ end {pmatrix} \ rightarrow (r3 \ leftrightarrow r1) \правая стрелка \ begin {pmatrix} 1 & 1 & -1 & | 1 \\ 3 & 2 & 1 & | 1 \\ 5 & 3 & 4 & | 2 \ end {pmatrix} \ rightarrow \ left \ {\ begin {array} {c} r2-3r1 \\ r3-5r1 \ end {array} \ right.$$$ $$$ \ rightarrow \ begin {pmatrix} 1 & 1 & -1 & | & 1 \\ 0 & -1 & 4 & | & -2 \\ 0 & -2 & 9 & | & -3 \ end {pmatrix} \ rightarrow r3-2r2 \ rightarrow \ begin {pmatrix} 1 & 1 & -1 & | & 1 \\ 0 & -1 & 4 & | & -2 \\ 0 & 0 & 1 & | & 1 \ end {pmatrix} $$$ Эта система уже является эшелонированной, поэтому мы можем ее решить. Так мы получили следующую систему: $$$ \ left \ {\ begin {array} {c} x + y-z = 1 \\ -y + 4z = -2 \\ z = 1 \ end {array} \ right.$$$ Решение: $$$ z = 1 \\ y = 6 \\ x = -4 $$$ Следовательно, это совместимая детерминированная система.

А теперь изучим систему $$$ \ left \ {\ begin {array} {c} 2x-5y + 4z + uv = -3 \\ x-2y + z-u + v = 5 \\ x-4y + 6z + 2 + v = 10 \ end {array} \ right. $$$

Это мы переписываем как $$$ \ begin {pmatrix} 2 & -5 & 4 & 1 & -1 & | & -3 \\ 1 & -2 & 1 & -1 & 1 & | & 5 \\ 1 & -4 & 6 & 2 & 1 & | & 10 \ end {pmatrix} $$$

Делаем следующие шаги $$$ \ begin {pmatrix} 2 & -5 & 4 & 1 & -1 & | & -3 \\ 1 & -2 & 1 & -1 & 1 & | & 5 \\ 1 & -4 & 6 & 2 & 1 & | & 10 \ end {pmatrix} \ rightarrow (r2 \ leftrightarrow r1) \ rightarrow $$$ $$$ \ begin {pmatrix} 1 & -2 & 1 & -1 & 1 & | & 5 \\ 2 & -5 & 4 & 1 & -1 & | & -3 \\ 1 & -4 & 6 & 2 & 1 & | & 10 \ end {pmatrix} \ rightarrow \ left \ {\ begin {array} {c} r2-2r1 \\ r3-r1 \ end {array} \ right.\ rightarrow $$$ $$$ \ begin {pmatrix} 1 & -2 & 1 & -1 & 1 & | & 5 \\ 2 & -5 & 4 & 1 & -1 & | & -3 \\ 1 & -4 & 6 & 2 & 1 & | & 10 \ end {pmatrix} \ rightarrow r3-2r2 \ rightarrow $$$ $$$ \ rightarrow \ begin {pmatrix} 1 & -2 & 1 & -1 & 1 & | & 5 \\ 0 & -1 & 2 & 3 & -3 & | & -13 \\ 0 & 0 & 1 & -3 & 6 & | & 31 \ end {pmatrix} $$$

и получаем $$ z-3u + 6v = 31 $$.

В этом случае нам нужно присвоить любое значение $$ u $$ и $$ v $$, а затем найти соответствующие значения $$ z $$, $$ y $$ и $$ x $$, все из их согласно $$ u $$ и $$ v $$.Следовательно, это совместимая неопределенная система.

Наконец, давайте посмотрим на пример неопределенной системы $$$ \ left \ {\ begin {array} {c} x + yz = 1 \\ 3x + 2y + z = 1 \\ 5x + 3y + 4z = 2 \\ -2x-y + 5z = 6 \ end {массив} \ right. $$$ Это мы переписываем: $$$ \ begin {pmatrix} 1 & 1 & -1 & | 1 \\ 3 & 2 & 1 & | 1 \\ 5 & 3 & 4 & | 2 \\ -2 & -1 & 5 & | 6 \ конец {pmatrix} $$$ И делаются следующие шаги: $$$ \ begin {pmatrix} 1 & 1 & -1 & | 1 \\ 3 & 2 & 1 & | 1 \\ 5 & 3 & 4 & | 2 \\ -2 & -1 & 5 & | 6 \ конец {pmatrix} \ rightarrow \ left \ {\ begin {array} {c} r2-3r1 \\ r3-5r1 \\ r4 + 2r1 \ end {array} \ right.\ rightarrow \ begin {pmatrix} 1 & 1 & -1 & | & 1 \\ 0 & -1 & 4 & | & -2 \\ 0 & -2 & 9 & | & -3 \\ 0 & 1 & 3 & | & 8 \ end {pmatrix} \ rightarrow $$$ $$$ \ left \ {\ begin {array} {c} r3-2r2 \\ r4 + r2 \ end {array} \ right. \ rightarrow \ begin {pmatrix} 1 & 1 & -1 & | & 1 \\ 0 & -1 & 4 & | & -2 \\ 0 & 0 & 1 & | & 1 \\ 0 & 0 & 7 & | & 6 \ end {pmatrix} \ rightarrow r4-7r3 \ rightarrow $$$ $$$ \ begin {pmatrix} 1 & 1 & -1 & | & 1 \\ 0 & -1 & 4 & | & -2 \\ 0 & 0 & 1 & | & 1 \\ 0 & 0 & 0 & | & -1 \ end {pmatrix} $$$

Чтобы увидеть несовместимость: $$ 0 = -1 $$.

Эта система несовместима.

Однородные системы

Если система с $$ m $$ уравнениями и $$ n $$ имеет все постоянные члены, равные нулю, то говорят, что она однородна.

Он допускает только тривиальное решение $$$ x_1 = x_2 = \ ldots = x_n = 0 $$$

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

Исключение Гаусса в Python: иллюстрация и реализация

Привет, кодеры !! В этой статье мы узнаем об исключении Гаусса в Python. Сначала мы поймем, что это означает, изучим его алгоритм, а затем реализуем его на Python. Итак, приступим!

Что такое метод исключения Гаусса?

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

  • Замена двух строк
  • Умножение строки на ненулевое число
  • Добавление кратного одной строки к другой строке

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

Иллюстрация исключения Гаусса на примере:

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

  • 2x + y – z = 8 ………………….L1
  • -3x – y + 2z = -11 ………… ..L2
  • -2x + y + 2z = -3 ………… ..L3

Расширенная матрица вышеуказанной системы уравнений будет быть:

Наша цель – сделать нижний левый угол матрицы максимально заполненным нулями. Для этого выполним последовательность операций.

L2 + 3 / 2L1 -> L2
L3 + L1 -> L3

Когда мы выполняем приведенное выше уравнение для расширенной матрицы, мы получаем:

Теперь перейдем к следующему этапу работы со строками.

L3 + -4L2 -> L3

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

L2 + 1 / 2L3 -> L2
L1 – L3 -> L1

Выполнив указанную выше операцию, мы получим следующую матрицу:

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

2L2 -> L2
-L3 -> L3

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

L1 – L2 -> L1
1/2 L2 -> L1

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

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

Реализация на Python:

 импортировать numpy как np
import sys

n = int (input ('Введите количество неизвестных:'))
a = np. нули ((n, n + 1))
x = np. нули (n)
print ('Введите коэффициенты расширенной матрицы:')
для i в диапазоне (n):
    для j в диапазоне (n + 1):
        a [i] [j] = float (input ('a [' + str (i) + '] [' + str (j) + '] ='))
для i в диапазоне (n):
    если [i] [i] == 0.0:
        sys.exit ('Обнаружено деление на ноль!')
        
    для j в диапазоне (i + 1, n):
        соотношение = a [j] [i] / a [i] [i]
        
        для k в диапазоне (n + 1):
            a [j] [k] = a [j] [k] - соотношение * a [i] [k]

x [n-1] = a [n-1] [n] / a [n-1] [n-1]

для i в диапазоне (n-2, -1, -1):
    x [i] = a [i] [n]
    
    для j в диапазоне (i + 1, n):
        x [i] = x [i] - a [i] [j] * x [j]
    
    x [i] = x [i] / a [i] [i]

print ('\ nРешение:')
для i в диапазоне (n):
    print ('X% d =% 0.2f '% (i, x [i]), end =' \ t ')
 

Выход и объяснение:

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

  • Сначала мы импортировали необходимые библиотеки, которые будем использовать в нашей программе.
  • Затем мы спросили у пользователя количество неизвестных переменных, которые мы храним в переменной «n».
  • После этого мы создали numpy-массив «a» размера nx (n + 1) и инициализировали его нулем. Мы будем хранить нашу расширенную матрицу в этом массиве.
  • Другой массив «x» размера n также создается и инициализируется нулем. Мы будем использовать этот массив для хранения вектора решения.
  • Затем мы использовали цикл для получения входных данных расширенной матрицы.
  • После этого мы применили метод исключения Гаусса.
  • Если какой-либо из коэффициентов равен 0, возникает ошибка, поскольку деление на ноль невозможно.
  • После этого мы применяем метод обратной подстановки, чтобы получить желаемый результат.

Обязательно прочитать

Вывод:

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

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

Счастливого питонинга!

Связанные

7.8 Практический пример: Гауссово исключение

7.8 Пример: Гауссовское исключение

Далее: 7.9 Резюме Up: 7 Высокопроизводительный Fortran Пред .: 7.7 Проблемы с производительностью

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

где A известная матрица размером N N , х требуется вектор решения и б – известный вектор размером N . Этот пример часто используется при обсуждении HPF как он показывает преимущества циклических распределений.Метод продолжается в два этапа:

  1. Гауссово исключение. Исходная система уравнений приведена к верхнетреугольной форме

    где U матрица размером N N в котором все элементы ниже диагонали равны нулю, а элементы диагонали имеют значение 1.

  2. Обратная подстановка. Новая система уравнений решается для получения значения x .


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

Этап алгоритма исключения Гаусса включает Н-1 шаги. В базовом алгоритме i -й шаг исключает ненулевое поддиагональные элементы в столбце и путем вычитания i th ряд из каждого ряда j в диапазоне [i + 1, n] , в каждом случае масштабирование i -й ряд на множитель так, чтобы получилось элемент ноль.Следовательно, алгоритм просматривает матрица из верхнего левого угла в нижний правый угол, оставляя ноль за ней поддиагональные элементы (рисунок 7.10).

Для обеспечения числовой устойчивости этот базовый алгоритм модифицирован так, чтобы вместо того, чтобы проходить по строкам по порядку, он выбирает на шаге и строка в диапазоне [i, n] с самым большим элементом в столбце и . Эта строка (называемая опорной точкой ) заменяется строкой и перед выполнением вычитаний.

Программа 7.7 ​​является HPF-реализацией этого алгоритм. Для эффективности эта программа поддерживает вектор б в N + 1 -й столбец массива A . Первый do-loop реализует метод исключения Гаусса. Используется внутренняя функция MAXLOC. чтобы определить сводную строку. Вместо того, чтобы выполнять явный своп с рядом и , косвенный массив с именем indx используется для отслеживать фактические индексы выбранных строк. Этот массив обновляется после определения точки поворота.Следующий оператор вычисляет N масштабных коэффициентов; обратите внимание, что вычисление может быть выполнено с одним массивом назначение. Наконец, оператор FORALL выполняет вычитания. Маска гарантирует, что вычитание будет выполняться только для строк, которые ранее не были выбраны как сводные ( Indx (j) .EQ.0). После завершения цикла выполнения второй FORALL используется для преобразования матрицы в верхнюю треугольную форму.

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


Рисунок 7.11: Обмен данными и вычисления на различных этапах алгоритма исключения Гаусса HPF. Стрелки представляют коммуникации, а затенение указывает задачи, связанные с вычислениями в каждая фаза. Пять этапов описаны в Раздел 7.8.

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

  1. Оператор MAXLOC включает операцию сокращения с помощью N задачи в и -й столбец.
  2. Максимальное значение, определяемое сокращением (max_indx), должно транслироваться в пределах и -й столбец, так как он необходим для расчет масштабных коэффициентов.
  3. Для вычисления масштабных коэффициентов (массив Fac) требуется N независимые операции, по одной для каждой задачи в i th столбец.
  4. Масштабный коэффициент (Fac (j)) и значение основной строки (Row (k)) должны транслироваться в каждом столбце и строке соответственно, поскольку они необходимы для обновления.
  5. Оператор FORALL включает в себя независимые операции, по одному на задание.

Изучая этот алгоритм, мы видим, что он имеет два интересных атрибуты. Во-первых, в общении мало места за пределами тот факт, что трансляции и сокращения выполняются по строкам и столбцы. Во-вторых, вычисления имеют тенденцию быть кластеризованными: на каждом этапе большая часть вычислений выполняется задачами в одной строке и столбец (перед FORALL) и в правом нижнем углу (ФОРАЛЛ).Эти атрибуты могут быть использованы при разработке директивы распределения данных для завершения параллельного алгоритма.

Во многих задачах, связанных с сеткой, мы предпочитаем использовать БЛОК. распределение основных структур данных, потому что это уменьшает коммуникационные требования за счет улучшения местности. Однако в Проблема исключения Гаусса, БЛОК-распределение не имеет коммуникативные преимущества; кроме того, это приводит к тому, что многие процессоры простаивает, особенно на более поздних этапах вычислений.Напротив, Распределение CYCLIC разбрасывает вычисления по многим процессорам а значит, сокращает время простоя. Следовательно, мы могли бы использовать следующие данные директивы по распространению.

! HPF $ ALIGN Row (j) WITH A (1, j)
        ! HPF $ ВЫРАВНИТЬ X (i) С A (i, N + 1)
        ! HPF $ ДИСТРИБУТ A (*, ЦИКЛИКА)
 

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

! HPF $ ALIGN Row (j) WITH A (1, j)
        ! HPF $ ВЫРАВНИТЬ X (i) С A (i, N + 1)
        ! HPF $ ДИСТРИБУТ A (ЦИКЛИЧЕСКИЙ, ЦИКЛИЧЕСКИЙ)
 


Далее: 7.9 Резюме Up: 7 Высокопроизводительный Fortran Предыдущее: 7.7 Проблемы с производительностью

© Авторские права, 1995, Ян Фостер,
Линейная алгебра

– зачем использовать метод исключения Гаусса-Джордана вместо исключения Гаусса, Различия

Следующий пример, часть Поиск последовательности элементарных матриц дополняет идею @ Xoque55


Целевая матрица $$ \оставил[ \ begin {array} {cc | cc} 2 и 4 \\ 1 и 1 \\ \ end {массив} \верно] $$

Используйте элементарные операции со строками для исключения Гаусса.$ \ color {blue} {Blue} $ окрашивание обозначает измененные элементы в выходной матрице.


Рядная эшелонированная форма

Формируют расширенную матрицу

$$ \оставил[ \ begin {array} {c | c} \ mathbf {A} & b \ end {массив} \верно] знак равно \оставил[ \ begin {array} {cc | c} 2 и 4 и b_ {1} \\ 1 & 1 & b_ {2} \\ \ end {массив} \верно]

$

Нормализовать строку 1: $$ \оставил[ \ begin {array} {cc} \ frac {1} {2} & 0 \\ 0 и 1 \\ \ end {массив} \верно] % \оставил[ \ begin {array} {cc | c} 2 и 4 и b_ {1} \\ 1 & 1 & b_ {2} \\ \ end {массив} \верно] знак равно \оставил[ \ begin {array} {cc | c} \ color {blue} {1} & \ color {blue} {2} & \ frac {1} {2} b_ {1} \\ 1 & 1 & b_ {2} \\ \ end {массив} \верно]

$

Очистить столбец 1 $$ \оставил[ \ begin {array} {rc} 1 & 0 \\ -1 и 1 \\ \ end {массив} \верно] % \оставил[ \ begin {array} {cc | c} \ color {blue} {1} & \ color {blue} {2} & \ frac {1} {2} b_ {1} \\ 1 & 1 & b_ {2} \\ \ end {массив} \верно] знак равно \оставил[ \ begin {array} {cr | c} 1 и 2 & \ frac {1} {2} b_ {1} \\ \ color {blue} {0} & \ color {blue} {- 1} & b_ {2} – \ frac {1} {2} b_ {1} \\ \ end {массив} \верно]

$

Система может быть решена обратной заменой.

Пониженная форма рядов

Процесс восстановления $$ % \оставил[ \ begin {array} {c | c} \ mathbf {A} & \ mathbf {I} \ end {массив} \верно] % \ qquad \ Rightarrow \ qquad % \оставил[ \ begin {array} {c | c} \ mathbf {E_ {A}} и \ mathbf {R} \ end {массив} \верно]

$

Формируют расширенную матрицу

$$ \оставил[ \ begin {array} {c | c} \ mathbf {A} & \ mathbf {I} \ end {массив} \верно] знак равно \оставил[ \ begin {array} {cc | cc} 2 и 4 и 1 и 0 \\ 1 и 1 и 0 и 1 \\ \ end {массив} \верно]

$

Нормализовать строку 1: $$ \оставил[ \ begin {array} {cc} \ frac {1} {2} & 0 \\ 0 и 1 \\ \ end {массив} \верно] % \оставил[ \ begin {array} {cc | cc} 2 и 4 и 1 и 0 \\ 1 и 1 и 0 и 1 \\ \ end {массив} \верно] знак равно \оставил[ \ begin {array} {cc | cc} \ color {blue} {1} & \ color {blue} {2} & \ frac {1} {2} & 0 \\ 1 и 1 и 0 и 1 \\ \ end {массив} \верно]

$

Очистить столбец 1 $$ \оставил[ \ begin {array} {rc} 1 & 0 \\ -1 и 1 \\ \ end {массив} \верно] % \оставил[ \ begin {array} {cc | cc} 1 и 2 & \ frac {1} {2} & 0 \\ 1 и 1 и 0 и 1 \\ \ end {массив} \верно] знак равно \оставил[ \ begin {array} {cr | rc} 1 и 2 & \ frac {1} {2} & 0 \\ \ color {blue} {0} & \ color {blue} {- 1} & – \ frac {1} {2} & 1 \\ \ end {массив} \верно]

$

Нормализовать строку 2 $$ \оставил[ \ begin {array} {cr} 1 & 0 \\ 0 & -1 \\ \ end {массив} \верно] % \оставил[ \ begin {array} {cc | cr} 1 и 2 & \ frac {1} {2} & 0 \\ 0 & 1 & \ frac {1} {2} & -1 \\ \ end {массив} \верно] знак равно \оставил[ \ begin {array} {cc | cr} 1 и 2 & \ frac {1} {2} & 0 \\ \ color {blue} {0} & \ color {blue} {1} & \ frac {1} {2} & -1 \\ \ end {массив} \верно]

$

Очистить столбец 2 $$ \оставил[ \ begin {array} {cr} 1 & -2 \\ 0 и 1 \\ \ end {массив} \верно] % \оставил[ \ begin {array} {cc | cr} 1 и 2 & \ frac {1} {2} & 0 \\ 0 & 1 & \ frac {1} {2} & -1 \\ \ end {массив} \верно] знак равно \оставил[ \ begin {array} {cc | rr} \ color {blue} {1} & \ color {blue} {0} & – \ frac {1} {2} & 2 \\ 0 & 1 & \ frac {1} {2} & -1 \\ \ end {массив} \верно] $$ Результат $$ \оставил[ \ begin {array} {c | c} \ mathbf {E_ {A}} и \ mathbf {R} \ end {массив} \верно] знак равно \оставил[ \ begin {array} {cc | rr} 1 & 0 & – \ frac {1} {2} & 2 \\ 0 & 1 & \ frac {1} {2} & -1 \\ \ end {массив} \верно]

$

Решение $$ \ mathbf {A} x = b \ quad \ Rightarrow \ quad х = \ mathbf {A} ^ {- 1} б \ quad \ Rightarrow \ quad x = \ frac {1} {2} \ left [ \ begin {array} {rr} -1 и 4 \\ 1 & -2 \\ \ end {массив} \верно] % \оставил[ \ begin {array} {c} б_ {1} \\ Би 2} \\ \ end {массив} \верно] \ quad \ Rightarrow \ quad х = \оставил[ \ begin {array} {l} – \ frac {1} {2} b_ {1} + 2b_ {2} \\ \ phantom {-} \ frac {1} {2} b_ {1} – b_ {2} \\ \ end {массив} \верно]

$

Произведение редукционных матриц

Произведение последовательности матриц редукции является обратным: $$ % четыре \оставил[ \ begin {array} {cr} 1 & -2 \\ 0 и 1 \\ \ end {массив} \верно] % в третьих \оставил[ \ begin {array} {cr} 1 & 0 \\ 0 & -1 \\ \ end {массив} \верно] % второй \оставил[ \ begin {array} {rc} 1 & 0 \\ -1 и 1 \\ \ end {массив} \верно] % первый \оставил[ \ begin {array} {cc} \ frac {1} {2} & 0 \\ 0 и 1 \\ \ end {массив} \верно] знак равно \оставил[ \ begin {array} {rr} – \ frac {1} {2} & 2 \\ \ frac {1} {2} & -1 \\ \ end {массив} \верно] знак равно \ mathbf {A} ^ {- 1}

$ .

Оставить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *