Решение линейных систем методом Гаусса Линейное уравнение, связывающее между собой неизвестные u, V, w, z, имеет вид 3u + 7v + 6w + 2z = 15 то есть каждое неизвестное умножается на какое-нибудь число «коэффициент при неизвестном»






НазваниеРешение линейных систем методом Гаусса Линейное уравнение, связывающее между собой неизвестные u, V, w, z, имеет вид 3u + 7v + 6w + 2z = 15 то есть каждое неизвестное умножается на какое-нибудь число «коэффициент при неизвестном»
страница2/4
Дата публикации05.03.2016
Размер0.58 Mb.
ТипРешение
e.120-bal.ru > Математика > Решение
1   2   3   4


Из 2-й и 3-й строки вычтем удвоенную 1-ю (двукратное применение свойства 4.. ):

w y z x Прав.части

1

4

6

8

164

0

-5

-6

-10

-174

0

-6

-8

-13

-223

Поменяем знаки у 2-го и 3-го уравнения (свойство 3.. ):


w y z x Прав.части

1

4

6

8

164

0

5

6

10

174

0

6

8

13

223

Видим, что второй диагональный элемент не равен нулю, то есть можно продолжать прямой ход метода Гаусса. Теперь надо создавать нули под диагональю не с помощью 1-го, а с помощью 2-го уравнения. Умножим 2-е уравнение на 6, а 3-е – на 5, чтобы сравнялись вторые коэффициенты:

w y z x Прав.части

1

4

6

8

164

0

30

36

60

1044

0

30

40

65

1115

Из 3-го уравнения вычтем 2-е (свойство 4.. ). При этом под диагональю создастся еще один нуль, а нули, созданные ранее, сохранятся. Затем приводим второе уравнение в предыдущее состояние путем деления его на 5. Получаем:

w y z x Прав.части

1

4

6

8

164

0

5

6

10

174

0

0

4

5

71


На этом заканчивается прямой ход. При его выполнении все числа остались целыми. Свободным неизвестным оказалось «x» , но при другом способе осуществления прямого хода свободное неизвестное могло бы оказаться другим. Однако количество свободных неизвестных не зависит от способа выполнения прямого хода. Переходим от матричной записи системы к треугольному виду (и затем осуществляем обратный ход метода Гаусса):

w +4y +6z = 164 -8x;

5y + 6z = 174 -10x;

4z = 71 -5x.

Отсюда z = (71–5x)/4, y = (174–10x–6z)/5 = (135–5x)/10 = (27–x)/2,

w = 164–8x–4y–6z = 164–8x –4(27–x)/2–6(71–5x)/4 = (7+3x)/2.

Формулы, выделенные жирным шрифтом, подставляем в уравнение, выражающее полную стоимость покупок:

337x + 205y + 330z + 141w = 9353;

337x + 205*(27-x)/2 + 330*(71-5x)/4 + 141*(7+3x)/2 = 9353;

337x – (205/2)x – (330*5/4)x + (141*3/2) = 9353 – 205*27/2 – 330*71/4 – 141*7/2;

33,5x = 234,5; x=7.

Таким образом, если эта задача имеет решения, то в каждом из них обязательно будет x=7. Линейная система, которая получилась при решении этой задачи, обязательно имеет единственное решение (его мы получим, подставляя x=7 в указанные выше уравнения, выделенные жирным шрифтом). Однако не всякое решение нам подойдет по физическому смыслу этой задачи: переменные x, y, z, w обязательно должны быть целыми неотрицательными числами. «К счастью», все они являются именно такими:

x=7, y=(27–7)/2 = 10, z=(71–5*7)/4 = 9, w=(7+3*7)/2 = 14.

В данном случае, конечно, счастье тут ни при чем – задача решалась для специально подобранных данных. Если изменить одну из правых частей (например, вместо количества вершин 210 взять 140), то поставленная задача не имеет решения. Метод Гаусса приводит в этом случае к формуле

z=(–390–5x)/10,

из которой следует, что при неотрицательном “x” будет отрицательным “z”, что недопустимо.
ПРИМЕР 2. Рассмотрим теперь задачу о восстановлении магического квадрата (определение см.ниже), в которой количество неизвестных велико, но зато матрица системы является «разреженной» (то есть содержит очень много нулей). В этом случае приходится часто менять местами столбцы, что весьма утомительно. Тогда рекомендуется применять метод Гаусса «с воображаемой перестановкой столбцов», особенно полезный при вычислениях не на компьютере, а на бумаге.

Сначала дадим определение, что такое магический квадрат.
Магический квадрат – это квадратная матрица порядка N, заполненная натуральными числами от 1 до N2, которые расположены таким образом, что сумма чисел по каждому столбцу одинакова, по каждой строке одинакова и по каждой из диагоналей (а их имеется две) одинакова. В классическом случае сумма по строке равна сумме по диагонали (и, конечно, сумма по строке такая же, как сумма по столбцу – ведь она обязана равняться числу S/N, где S – сумма натуральных чисел от 1 до N2. Число S/N называется «магическим значением» данного квадрата. Легко вычислить, что оно равно N(N2+1)/2. При N=1 магический квадрат тривиален. При N=2 он не существует, так как суммы по строкам должны равняться пяти, а расставляемые числа равны 1, 2, 3, 4. По строкам (или по столбцам) должны располагаться числа 1+4 и 2+3, но тогда по столбцам (или по строкам) должны располагаться либо пары 1+2, 4+3, – либо пары 1+3, 2+4. Ни в одном случае из этих двух не получается магическое значение 5.

Для каждого из чисел N = 3, 4, 5, … магические квадраты существуют, причем в большом количестве вариантов. Например, для N=3 и N=4 они могут быть такими:

4 9 2 (магич. значение = 15) 1 15 14 4 (магич. значение = 34)

3 5 7 12 6 7 9

8 1 6 8 10 11 5

13 3 2 16
Интересно отметить, что оба этих квадрата получены математиками не путем подбора «наудачу» чисел от 1 до 9 (или, соответственно, от 1 до 16), а по строгому правилу, опираясь на запись этих чисел в исходном естественном порядке (то есть по строкам сверху вниз). Например, для конфигурации

1

2

3

4

5

6

7

8

9

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


При этом четыре числа (а именно: 1, 9, 7, 3) оказываются за пределами нового квадрата, а остальные пять расположены на нужном месте (то есть на месте, обеспечивающим магичность квадрата). Поворачивая новый квадрат 3х3 обратно на 45 градусов, получаем почти сформированный магический квадрат 3х3:

4




2




5




8




6

Зная, что магическое значение равно 15, легко догадаться, как именно надо расставить недостающие числа 1, 9, 7, 3 в пустых клетках квадрата.

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

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16
Числа, выделенные жирным шрифтом, образуют «кольцо», которое надо два раза повернуть (один раз – на 180 градусов относительно вертикальной оси, затем – на 180 градусов относительно горизонтальной оси). Остальные же числа надо оставить на том месте, где они и находились сначала. Заметьте, что сумма чисел по диагоналям с самого начала равнялась магическому числу 34. Эти числа так и останутся на прежних местах (квадрат с «замороженными» диагоналями).

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

Например, решим такую задачу. В магическом квадрате типа 4х4 известны числа, стоящие на диагоналях (те самые, что указаны выше). Неизвестные нам числа обозначим (x,y,z,u,v,w,s,t) , причем они следуют в порядке движения сверху вниз по строкам:

1 x y 4

z 6 7 u

v 10 11 w

13 s t 16
С помощью метода Гаусса доказать, что x=15, y=14, z=12, u=9, v=8, w=5, s=3, t=2.
Решение.

Так как по каждой строке и по каждому столбцу сумма равна 34, то мы получаем восемь линейных уравнений для восьми неизвестных. Это, конечно, не означает, что данная система имеет единственное решение. Кроме того, нам нужны не просто решения, а целые положительные решения. И не любые целые положительные, а только взятые (по одному разу каждое неизвестное) из множества (15, 14, 12, 9, 8, 5, 3, 2).

Итак, у нас получится линейная система, у которой неочевидно наличие решений (не получится ли уравнение типа «0=с», где с не равно нулю), а если наличие доказано, то не очевидно, сколько степеней свободы имеет множество решений, и можно ли, выбирая нужным образом свободные неизвестные, получить именно магический квадрат 4х4.

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

Запишем сначала уравнения по строкам и столбцам в обычном виде:
x+y = 34–5,

z+u = 34–13,

v+w = 34–21,

s+t = 34–29,

z+v = 34–14,

x+s = 34–16,

y+t = 34–18,

u+w = 34–20
Теперь выпишем расширенную матрицу системы:
x y z u v w s t Правые части:

1

1

0

0

0

0

0

0

29







1

1













21













1

1







13



















1

1

5







1




1










20

1
















1




18




1
















1

16










1




1







14


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

Сначала подчеркиваем число в левом верхнем углу в знак того, что данный диагональный элемент ненулевой. Затем с его помощью создаем нули под этим элементом. Для этого достаточно только к 6-му уравнению прибавить 1-е, умноженное на (–1). Проще говоря, вычитаем из 6-го уравнения 1-е:
x y z u v w s t Правые части:

1

1

0

0

0

0

0

0

29







1

1













21













1

1







13



















1

1

5







1




1










20

0

–1













1




-11




1
















1

16










1




1







14

Чтобы двигаться дальше, надо, чтобы 2-й диагональный элемент стал неравен нулю. Тут возможны три подхода: 1)поменять местами 1-е и 6-е уравнения, либо 2)поменять местами 2-й и 3-й столбец, либо 3)поменять местами 2-й и 4-й столбец. Это значит, что три разных студента, решающие эту задачу методом Гаусса, получат разные значения коэффициентов преобразованной матрицы и даже, может быть, разные наборы свободных неизвестных; но множества решений, полученных каждым из студентов, будут совпадать.

Мы выберем второй подход:

x z y u v w s t Правые части:

1

0

1

0

0

0

0

0

29




1

0

1













21




0

0




1

1







13




0

0










1

1

5




1

0




1










20

0

0

–1










1




-11




0

1













1

16




0

0

1




1







14

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

x z y u v w s t Правые части:

1

0

1

0

0

0

0

0

29




1

0

1













21




0

0




1

1







13




0

0










1

1

5




0

0

–1

1










–1

0

0

–1










1




-11




0

1













1

16




0

0

1




1







14

Теперь желательно поменять местами 3-й и 5-й столбец, чтобы третий диагональный элемент стал не равен нулю. Но можно сделать это не фактически, а «мысленно», просто подчеркнув коэффициент при неизвестном “v” в 3-м уравнении. Затем обычным методом мы будем создавать нули под подчеркнутым элементом с помощью свойства 4.. Конкретно для этого достаточно из пятого уравнения вычесть третье, так как матрица разреженная. Так же можно поступать и далее, подчеркивая все новые и новые ненулевые элементы, но пока не переставляя столбцы. Запутаться при этом невозможно, так как если подчеркнутый элемент стоит, скажем, на 14-м месте в 6-м уравнении, то «по закону» ему положено находиться на 6-м месте в 6-м уравнении. Прямой ход метода Гаусса, таким образом, продолжается до конца, но с «мысленной» перестановкой столбцов. Затем можно сразу сделать все недоделанные перестановки столбцов, чтобы по диагонали шли сплошь неравные нулю элементы.

Итак, из 5-го уравнения вычитаем 3-е. При этом, однако, надо вычитать полностью все третье уравнение из всего пятого уравнения, то есть просматривать коэффициенты не только справа от подчеркнутого элемента, но и слева от него (ранее все левые элементы автоматически равнялись нулю, так при создании очередного нуля под диагональю прежние нули сохранялись). Чтобы не отвлекать своего внимания, все нули в матрице заменим пустыми клетками (это – так называемые «подразумеваемые нули»).

x z y u v w s t Правые части:

1




1
















29




1




1













21













1

1







13



















1

1

5










–1




–1







-14







–1










1




-11







1













1

16










1




1







14

В качестве 4-го подчеркнутого элемента возьмем коэффициент при “s” в 4-м уравнении и создадим нули под ним. Но три нуля уже и так созданы. Чтобы получить четвертый, от 6-го уравнения отнимем 4-е:

x z y u v w s t Правые части:

1




1
















29




1




1













21













1

1







13



















1

1

5










–1




–1







-14







–1













–1

-16







1













1

16










1




1







14

Пятый диагональный элемент получим, подчеркивая коэффициент при “u” в пятом уравнении, после чего становится ясно, что прибавляя к 8-му уравнению 5-е, мы получаем уравнение типа «0=0», которое надо отбросить. Шестой диагональный элемент получим, подчеркнув коэффициент при “y” в шестом уравнении. Прибавляя к 7-му уравнению 6-е, получаем «0=0». Значит, 7-е уравнение тоже надо отбросить. Итак, в этой системе только 6 независимых уравнений:

x z y u v w s t Правые части:

1




1
















29




1




1













21













1

1







13



















1

1

5










–1




–1







-14







–1













–1

-16























































Остались неподчеркнутыми элементы только в столбцах “w” и “t”. Эти неизвестные следует считать свободными. Это значит, что система имеет бесконечное количество решений с двумя степенями свободы. Однако далеко не каждое решение позволяет получить магический квадрат!

Таким образом, для этой линейной системы (см. начало статьи) N=8, k=8, n = 6. Расставляя столбцы так, чтобы все 6 подчеркнутых элементов шли по диагонали, и отбрасывая последние два уравнения, а также умножая «для красоты» 5-е и 6-е уравнение на (–1), получаем:

x z v s u y w t Правые части:

1













1







29




1







1










21







1










1




13










1










1

5













1




1




14
















1




1

16

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

x+y =29,

z+u = 21,

v+w = 13,

s+t = 5,

u+w = 14,

y+t = 16.

Двигаясь снизу вверх, выражаем все неизвестные через “w” и “t”:

y = 16–t,

u = 14–w,

s = 5–t,

v = 13–w,

z = 21-u = 21-(14-w) = 7+w,

x = 29-y = 29-(16-t) = 13+t.

На этом стандартная часть решения (метод Гаусса) заканчивается, и надо применить другие соображения. Ясно, что нам надо выбрать целые положительные значения свободных неизвестных w, t таким образом, чтобы главные неизвестные x, z, v, s, u, y тоже были бы целыми положительными (это условие необходимо, но не достаточно; но мы пока остановимся именно на нем). Из уравнения s = 5-t следует, что t может быть равно лишь 1, 2, 3, 4. Напомним, что в исходной формулировке задачи требовалось доказать, что x=15, y=14, z=12, u=9, v=8, w=5, s=3, t=2. Поэтому из этих четырех возможных значений t мы вправе выбрать t=2 (на то оно и свободное неизвестное!). Аналогично мы можем выбрать w=5 (как требуется в условии). Но в этом месте и заканчивается наша «свобода выбора», а остальные неизвестные придется выбирать не «как требуется в задаче», а как диктуют вполне определенные формулы общего решения, полученные методом Гаусса. Подойдут ли нам полученные значения остальных неизвестных, пока неизвестно. Вычисления по формулам дают: y=14, u=9, s=3, v=8 (все это пока соответствует требуемым значениям). Далее, z=7+5=12 и, наконец, x=13+2=15. Все требуемые значения подтверждены, и задача решена. Но такое решение нельзя признать безупречным, так как оно неполное. А может, при других значениях t,w получится еще одно решение, то есть еще один магический квадрат? Попытаемся найти его. Так как s=5-t, то можно брать только t=1, t=2, t=3, t=4 (далее s перестает быть положительным). Но значения 1 и 4 использованы на диагоналях квадрата, а значение 2 мы уже брали. Осталось исследовать значение 3. При таком выборе t получаем, что y=16-t =13. Такое значение тоже уже использовано на диагонали квадрата. Следовательно, t=2. В качестве w мы взяли число 5. А могли ли мы взять другое число? Потенциально нам доступны только числа 2,3,5,8,9,12,14,15. Учитывая, что из них уже использованы t=2, y=16-t =14, s=5-t = 3, x=13+t = 15, а значение 5 использовать не следует, так как мы хотим получить в качестве w что-то новое, у нас остаются только такие возможности для w: 8, 9, 12. Последнее число не подходит, так как получится z=7+w=19. Не подходит и 9 (z=7+w=16; это число уже использовано на диагонали). Наконец, при w=8 получается z=15, что уже использовано при нахождении значения “x”.

Теперь видно, что не только можно было взять свободные неизвестные t=2,w=5, но и нужно было это сделать. Иначе квадрат не будет магическим. Ну, наконец-то! Только осталось в душе ощущение, что нами решена несоразмерно громоздкая задача.

Чтобы читатели поняли, в чем тут суть дела (и немного отдохнули), я расскажу историю, которая однажды произошла с американским изобретателем Эдисоном. Он, проживая летом на загородном участке, пригласил к себе двух своих хороших знакомых, над которыми он никоим образом не собирался подшутить. Но, подойдя к его дому, знакомые никак не могли открыть садовую калитку, которая открывалась очень туго, и, наконец, пыхтя, с трудом открыли ее вдвоем. Они пожаловались на это Эдисону, на что он благодушно сказал: «Это неудивительно! Ведь, открывая калитку, вы накачали в бочку, стоящую на крыше сарая, 10 литров воды». Вот и мы, применяя метод Гаусса к этой задаче, сделали гораздо больше, чем собирались. Поскольку этот метод выявляет все без исключения решения системы, то мы, фактически, доказали следующую теорему:
1   2   3   4

Похожие:

Решение линейных систем методом Гаусса Линейное уравнение, связывающее между собой неизвестные u, V, w, z, имеет вид 3u + 7v + 6w + 2z = 15 то есть каждое неизвестное умножается на какое-нибудь число «коэффициент при неизвестном» iconОсобенности применения модели Гордона при оценке стоимости объектов недвижимости
Ддп для определения стоимости неизнашиваемых активов [1 и др.]. По своей сути формула модели Гордона представляет собой сумму бесконечного...

Решение линейных систем методом Гаусса Линейное уравнение, связывающее между собой неизвестные u, V, w, z, имеет вид 3u + 7v + 6w + 2z = 15 то есть каждое неизвестное умножается на какое-нибудь число «коэффициент при неизвестном» iconЗадача рационального поведения потребителя на рынке и ее решение...
Экономические системы: структура, виды, историческое место. Способы и критерии типологизации экономических систем

Решение линейных систем методом Гаусса Линейное уравнение, связывающее между собой неизвестные u, V, w, z, имеет вид 3u + 7v + 6w + 2z = 15 то есть каждое неизвестное умножается на какое-нибудь число «коэффициент при неизвестном» iconЦель урока: подчеркнуть нарастающую необходимость современности «жить...
«природа — идеальный мир» (гармония природы, сбалансированность природных процессов «так было, есть и должно быть всегда!»)

Решение линейных систем методом Гаусса Линейное уравнение, связывающее между собой неизвестные u, V, w, z, имеет вид 3u + 7v + 6w + 2z = 15 то есть каждое неизвестное умножается на какое-нибудь число «коэффициент при неизвестном» iconНепрерывные случайные величины. Закон Гаусса. Правило 3-х сигм
Закон Гаусса. Пусть Х – значение непрерывной случайной величины, dx- малый интервал, то вероятность dP того, что Х находится в интервале...

Решение линейных систем методом Гаусса Линейное уравнение, связывающее между собой неизвестные u, V, w, z, имеет вид 3u + 7v + 6w + 2z = 15 то есть каждое неизвестное умножается на какое-нибудь число «коэффициент при неизвестном» iconРешение парадоксов и проблем экономической теории Единое решение:...
С помощью кусочно-непрерывного приближения и принципа неопределенного будущего, выведено уравнение прогнозирования. В качестве приложений...

Решение линейных систем методом Гаусса Линейное уравнение, связывающее между собой неизвестные u, V, w, z, имеет вид 3u + 7v + 6w + 2z = 15 то есть каждое неизвестное умножается на какое-нибудь число «коэффициент при неизвестном» iconПо следам викингов: поиски гена близнецовости джон Сент Клер*, М. Д. Голубовский**
Дз близнецы возникают из двух разных оплодотворенных яйцеклеток и различны между собой как братья и сестры. Сравнение мз и дз близнецов...

Решение линейных систем методом Гаусса Линейное уравнение, связывающее между собой неизвестные u, V, w, z, имеет вид 3u + 7v + 6w + 2z = 15 то есть каждое неизвестное умножается на какое-нибудь число «коэффициент при неизвестном» iconДипломная р абот а студента 5 курса В581
Охватывается функцией планирования. Единство планов значит общность финансовых целей и связь всех составляющих системы. Связь между...

Решение линейных систем методом Гаусса Линейное уравнение, связывающее между собой неизвестные u, V, w, z, имеет вид 3u + 7v + 6w + 2z = 15 то есть каждое неизвестное умножается на какое-нибудь число «коэффициент при неизвестном» icon1. Понятие и структура экономических систем общества
В переводе с греческого "система" означает некое целое, состоящее из частей, связанных между собой и образующих целостность

Решение линейных систем методом Гаусса Линейное уравнение, связывающее между собой неизвестные u, V, w, z, имеет вид 3u + 7v + 6w + 2z = 15 то есть каждое неизвестное умножается на какое-нибудь число «коэффициент при неизвестном» icon456080 Челябинская обл, г. Трёхгорный, ул. Ленина д. 8 кв. 14 sch109@trg ru
Общества процветают, когда убеждения и технологии согласны между собой; они приходят в упадок, когда неизбежные изменения убеждений...

Решение линейных систем методом Гаусса Линейное уравнение, связывающее между собой неизвестные u, V, w, z, имеет вид 3u + 7v + 6w + 2z = 15 то есть каждое неизвестное умножается на какое-нибудь число «коэффициент при неизвестном» iconРоссийская империя и Австро-Венгерская монархия
«Повседневность между боями: неизвестные фотографии венгерского графа Дюлы Каройи о Восточном фронте»






При копировании материала укажите ссылку © 2016
контакты
e.120-bal.ru
..На главную