Оптимизация решения системы линейных уравнений

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

Содержание:

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

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

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

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

Крамер предложил следующий метод решения СЛАУ: умножим главный определитель на для этого умножим все элементы первого столбца на эту неизвестную:

Второй столбец умножим на третий столбец — на -ый столбец — на и все эти произведения прибавим к первому столбцу, при этом произведение не изменится:

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

Определение: Определитель называется первым вспомогательным определителем СЛАУ.

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

31. Для того чтобы найти вспомогательный определитель i, надо в главном определителе СЛАУ заменить столбец i на столбец свободных коэффициентов.

Определение: Полученные выше соотношения называются формулами Крамера. Используя формулы Крамера, находят неизвестные величины Проанализируем полученные формулы:

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

Пример:

Решить СЛАУ методом Крамера

Решение:

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

Найдем главный определитель СЛАУ (раскрываем по первой строке)

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

Воспользуемся формулами Крамера

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

Выполним проверку Отсюда видно, что СЛАУ решена верно.

Матричный способ решения СЛАУ

Для решения СЛАУ матричным способом введем в рассмотрение матрицу, составленную из коэффициентов при неизвестных матpицы-столбцы неизвестных и свободных коэффициентов

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

Пример:

Решить СЛАУ матричным способом

Решение:

Введем в рассмотрение следующие матрицы

Найдем матрицу (см. Лекцию № 2): найдем детерминант матрицы А.

Пример:

Решение:

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

Отсюда находим, что х = 1; y = l; z = l.

Метод Гаусса

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

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

Обменяем в расширенной матрице первую и вторую строки местами, получим Приведем матрицу к треугольному виду, выполнив следующие преобразования: умножим элементы первой строки на (-2) и прибавим к соответствующим элементам второй строки Разделим все элементы второй строки на (-5), получим эквивалентную матрицу

Умножим элементы первой строки на (—1) и прибавим к соответствующим элементам третьей строки Разделим все элементы третьей строки на (-3), получим Таким образом, эквивалентная СЛАУ имеет вид (напомним, что первый столбец это коэффициенты при неизвестной х, второй — при неизвестной у, третий — при неизвестной z, а за вертикальной чертой находится столбец свободных коэффициентов):

Из первого уравнения находим, что х = 1.

Вывод: Из вышеизложенного материала следует, что вне зависимости от

способа решения СЛАУ всегда должен получаться один и тот же ответ.

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

Ранг матрицы. Теорема Кронекера-Капелли

Определение: Рангом матрицы называется наивысший порядок отличного от нуля минора этой матрицы.

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

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

Пример:

Найти ранг матрицы

Решение:

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

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

Следствия из теоремы Кронекера — Капелли

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

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

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

• Скалярное произведение и его свойства
• Векторное и смешанное произведения векторов
• Преобразования декартовой системы координат
• Бесконечно малые и бесконечно большие функции
• Критерий совместности Кронекера-Капелли
• Формулы Крамера
• Матричный метод
• Экстремум функции

При копировании любых материалов с сайта evkova.org обязательна активная ссылка на сайт www.evkova.org

Сайт создан коллективом преподавателей на некоммерческой основе для дополнительного образования молодежи

Сайт пишется, поддерживается и управляется коллективом преподавателей

Whatsapp и логотип whatsapp являются товарными знаками корпорации WhatsApp LLC.

Cайт носит информационный характер и ни при каких условиях не является публичной офертой, которая определяется положениями статьи 437 Гражданского кодекса РФ. Анна Евкова не оказывает никаких услуг.

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

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

Система линейных алгебраических уравнений с n неизвестными — это система уравнений вида

(1)

Слово система означает, что все уравнения рассматриваются как одно целое.

В общем случае у нас имеется m — уравнений, n — количество неизвестных. x₁, x₂,…, x_n — неизвестные, которые следует определить.

В системе (1) – фиксированные коэффициенты, b₁, b₂, …, b_m — свободные члены — предполагаются известными.

Система (1) называется однородной, если все её свободные члены равны нулю (b₁ = b₂ = … = b_m = 0), иначе — неоднородной.

Система (1) называется квадратной, если число m уравнений равно числу n неизвестных.

Задача состоит в том, чтобы найти такие которые удовлетворяют всем уравнениям (1).

В частном случае мы имеем одно линейное уравнение:

Конечно, такое уравнение легко решить, если предположить, что коэффициент не равен 0, имеем: = .

Очевидно, в общем случае имеются 3 варианта решений: система имеет ни одного решения, имеет одно решение, более одного решения.

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

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

Здесь A — это матрица системы, x — столбец неизвестных, а b — столбец свободных членов.

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

Рассмотрим, например, систему вида и поймем, как найти ее решение:

(2)

Предположим на минуту, что в первом уравнении y отсутствует, а во втором отсутствует x, тогда мы имели бы решение именно то решение, которое нам нужно.

Вопрос: как исходную систему привести к такому виду и можно ли это сделать.

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

От этих операций тождество не меняется.

В системе (2) у нас два тождества, домножим второе тождество на 2 и вычтем из первого, получим:

(3)

Формально у нас есть еще старое тождество , но оно нам не понадобится (подумайте, почему).

Система (3) точно такая же, как система (2).

Из второго уравнения системы (3) сразу получим:

Никто не мешает нам подставить это значение в первое уравнение:

Отсюда сразу находим, что

Итак, путем простых действий мы нашли, что система (2) может быть представлена в виде:

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

Метод Гаусса является одним из самых распространенных прямых методов решения систем линейных уравнений Ax = b:

Опишем этот метод в общем случае.

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

Это достигается следующей последовательностью преобразований (прямой ход).

Будем считать для удобства, что элемент a_ij исходной матрицы и компоненты вектора b_i есть, соответственно, элементы a_ij (1) первого шага преобразованной матрицы A₁ и преобразованного вектора b₁:A = A₁, b=b₁.

Далее, на втором шаге прибавим к второй строке первую, умноженную на

Аналогично поступим со всеми оставшимися строками, т.е. прибавим к каждой i-ой строке i=2,3. N, первую, умноженную на коэффициент

При этом соответственно изменится и вектор b1.

Таким образом, 2 шаг.

где

Прибавим к новой третьей строке новую вторую, умноженную на

То же самое сделаем с остальными строками 4,5. N, т.е. прибавим к i-ой строке вторую, умноженную на

Здесь

Поступая так и далее, на шаге N -1 получаем верхнетреугольную систему:

При этом, мы также получили матрицу C переводных коэффициентов, имеющую вид:

Решение полученной треугольной системы как легко видеть, имеет вид (обратный ход метода Гаусса):

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

Поэтому метод Гаусса обычно проводят с частичным выбором главного элемента, то есть после каждого шага (пусть это был k-й шаг) переставляют строки с номерами k,k+1. N таким образом, чтобы на месте kk оказался элемент наибольший из всех в k-ом столбце при m>k (при этом, естественно, переставляются и компоненты вектора b).

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

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

Опишем обратный ход метода Гаусса в несколько иной форме (треугольное разложение).

Введем матрицы M_k по правилу:

На каждом шаге метода Гаусса получается некоторая промежуточная матрица:

и вектор

Нетрудно видеть, что

Вопрос. Почему

Если производить также выбор главных элементов, то необходимо использовать оператор P перестановки индексов l и m, матричные элементы которого равны:

При применении оператора перестановки индексов к матрице слева, меняются местами строки матрицы и компоненты свободного вектора (PAx = Pb), если же его применить справа к матрице, то меняются местами ее столбцы и компоненты решения

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

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

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

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

Идея состоит в том, чтобы найти неподвижную точку матричного уравнения

(5)

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

При итерации в правой части уравнения заменяется, например, в методе Якоби (метод простой итерации) приближение, найденное на предыдущем шаге:

.

Термин неподвижная точка становится ясен, если вы внимательно посмотрите на уравнение (5), по самому своему смыслу величина Х является неподвижной точкой.

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

Обусловленность линейных систем, погрешность

При решении абстрактной задачи Ax = b, где A — оператор произвольной природы, важным моментом является корректность ее постановки.

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

Однако и непрерывная зависимость от входных данных может иметь свои нюансы.

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

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

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

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

Чем можно охарактеризовать количественно обусловленность для линейных систем?

Пусть A — квадратная NxN — матрица.

Рассмотрим задачу Ax = b.

Пусть также некоторая норма в пространстве R_N

Норма оператора A определяется стандартно:

Обозначим y = Ax и введем число m по правилу:

Величина называется числом обусловленности.

1. 
2. 
3. если A — диагональная, то (Для какой нормы, или для всех вышеприведенных?). Чем меньше число обусловленности C(A), тем лучше обусловлена система. Действительно, пусть вариация правой части, а соответствующее изменение решения.

Тогда справедливо следующее неравенство:

то

Аналогично, поскольку

Объединяя два неравенства, окончательно получаем для оценки погрешности:

Как решать систему уравнений

О чем эта статья:

8 класс, 9 класс, ЕГЭ/ОГЭ

Основные понятия

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

Уравнение — это математическое равенство, в котором неизвестна одна или несколько величин. Значение неизвестных нужно найти так, чтобы при их подстановке в исходное уравнение получилось верное числовое равенство.

Например, возьмем 3 + 4 = 7. При вычислении левой части получается верное числовое равенство, то есть 7 = 7.

Уравнением можно назвать, например, равенство 3 + x = 7 с неизвестной переменной x, значение которой нужно найти. Результат должен быть таким, чтобы знак равенства был оправдан, и левая часть равнялась правой.

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

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

Линейное уравнение с двумя переменными

Уравнение вида ax + by + c = 0 называется линейным уравнением с двумя переменными x и y, где a, b, c — числа.

Решением этого уравнения называют любую пару чисел (x; y), которая соответствует этому уравнению и обращает его в верное числовое равенство.

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

Вот алгоритм построения графика ax + by + c = 0, где a ≠ 0, b ≠ 0:

Дать переменной 𝑥 конкретное значение x = x₁, и найти значение y = y₁ при ax₁ + by + c = 0.

Дать x другое значение x = x₂, и найти соответствующее значение y = y₂ при ax₂ + by + c = 0.

Построить на координатной плоскости xy точки: (x₁; y₁); (x₂; y₂).

Провести прямую через эти две точки и вуаля — график готов.

Нужно быстро привести знания в порядок перед экзаменом? Записывайтесь на курсы ЕГЭ по математике в Skysmart!

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

Для ax + by + c = 0 можно сколько угодно раз брать произвольные значение для x и находить значения для y. Решений в таком случае может быть бесчисленное множество.

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

Из первого линейного уравнения a₁x + b₁y + c₁ = 0 можно получить линейную функцию, при условии если b₁ ≠ 0: y = k₁x + m₁. График — прямая линия.

Из второго ЛУ a₂x + b₂y + c₂ = 0 можно получить линейную функцию, если b₂ ≠ 0: y = k₂x + m₂. Графиком снова будет прямая линия.

Можно записать систему иначе:

Множеством решений первого ЛУ является множество точек, лежащих на определенной прямой, аналогично и для второго ЛУ. Если эти прямые пересекаются — у системы есть единственное решение. Это возможно при условии, если k₁ ≠ k₂.

Две прямые могут быть параллельны, а значит, они никогда не пересекутся и система не будет иметь решений. Это возможно при следующих условиях: k₁ = k₂ и m₁ ≠ m₂.

Две прямые могут совпасть, и тогда каждая точка будет решением, а у системы будет бесчисленное множество решений. Это возможно при следующих условиях: k₁ = k₂ и m₁ = m₂.

Метод подстановки

Разберем решение систем уравнений методом подстановки. Вот алгоритм при переменных x и y:

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

Подставить то, что получилось на место этой переменной в другое уравнение системы.

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

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

Записать ответ. Ответ принято записывать в виде пар значений (x; y).

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

Пример 1

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

x − y = 4
x + 2y = 10

Выразим x из первого уравнения:

x − y = 4
x = 4 + y

Подставим получившееся выражение во второе уравнение вместо x:

x + 2y = 10
4 + y + 2y = 10

Решим второе уравнение относительно переменной y:

4 + y + 2y = 10
4 + 3y = 10
3y = 10 − 4
3y = 6
y = 6 : 3
y = 2

Полученное значение подставим в первое уравнение вместо y и решим уравнение:

x − y = 4
x − 2 = 4
x = 4 + 2
x = 6

Ответ: (6; 2).

Пример 2

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

x + 5y = 7
3x = 4 + 2y

Сначала выразим переменную x из первого уравнения:

x + 5y = 7
x = 7 − 5y

Выражение 7 − 5y подставим вместо переменной x во второе уравнение:

3x = 4 + 2y
3 (7 − 5y) = 4 + 2y

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

3 (7 − 5y) = 4 + 2y
21 − 15y = 4 + 2y
21 − 15y − 2y = 4
21 − 17y = 4
17y = 21 − 4
17y = 17
y = 17 : 17
y = 1

Подставим значение y в первое уравнение и найдем значение x:

x + 5y = 7
x + 5 = 7
x = 7 − 5
x = 2

Ответ: (2; 1).

Пример 3

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

x − 2y = 3
5x + y = 4

Из первого уравнения выразим x:

x − 2y = 3
x = 3 + 2y

Подставим 3 + 2y во второе уравнение системы и решим его:

5x + y = 4
5 (3 + 2y) + y = 4
15 + 10y + y = 4
15 + 11y = 4
11y = 4 − 15
11y = −11
y = −11 : 11
y = −1

Подставим получившееся значение в первое уравнение и решим его:

x − 2y = 3
x − 2 (−1) = 3
x + 2 = 3
x = 3 − 2
x = 1

Ответ: (1; −1).

Метод сложения

Теперь решим систему уравнений способом сложения. Алгоритм с переменными x и y:

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

Складываем почленно левые и правые части уравнений системы.

Решаем получившееся уравнение с одной переменной.

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

Запишем ответ в в виде пар значений (x; y).

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

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

Решений в таком случае может быть бесчисленное множество. Придавая двум переменным различные значения, можно найти третье значение. Ответ принято записывать в виде тройки значений (x; y; z).

Если x, y, z связаны между собой тремя уравнениями, то образуется система трех ЛУ с тремя переменными. Для решения такой системы можно применять метод подстановки и метод сложения.

Решение задач

Разберем примеры решения систем уравнений.

Задание 1. Как привести уравнение к к стандартному виду ах + by + c = 0?

5x − 8y = 4x − 9y + 3

5x − 8y = 4x − 9y + 3

5x − 8y − 4x + 9y = 3

Задание 2. Как решать систему уравнений способом подстановки

Выразить у из первого уравнения:

Подставить полученное выражение во второе уравнение:

Найти соответствующие значения у:

Задание 3. Как решать систему уравнений методом сложения

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

1. Решаем полученное квадратное уравнение любым способом. Находим его корни:

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

1. Ответ: (1; 1), (1; -1).

Задание 4. Решить систему уравнений

Решим второе уравнение и найдем х = 2, х = 5. Подставим значение переменной х в первое уравнение и найдем соответствующее значение у.

Задание 5. Как решить систему уравнений с двумя неизвестными

При у = -2 первое уравнение не имеет решений, при у = 2 получается: