Знайти загальне рішення системи шляхом гауса. Метод Гаус для чайників: приклади рішень. Застосування методу Гауса в теорії ігор

Ще з початку XVI-XVIII століть математики посилено почали вивчати функції, завдяки яким так багато в нашому житті змінилося. Комп'ютерна технікабез цих знань просто не було б. Для вирішення складних завдань, лінійних рівнянь та функцій були створені різні концепції, теореми та методики вирішення. Одним з таких універсальних та раціональних способів та методик розв'язання лінійних рівнянь та їх систем став і метод Гаусса. Матриці, їхній ранг, детермінант - все можна порахувати, не використовуючи складних операцій.

Що являє собою СЛАУ

У математиці існує поняття СЛАУ - система лінійних рівнянь алгебри. Що ж вона є? Це набір m рівнянь з шуканими n невідомими величинами, які зазвичай позначаються як x, y, z, або x 1 , x 2 … x n, або іншими символами. Вирішити методом Гауса цю систему- означає знайти всі шукані невідомі. Якщо система має однакову кількість невідомих і рівнянь, вона називається системою n-го порядку.

Найбільш популярні методи вирішення СЛАУ

У навчальних закладах середньої освіти вивчають різноманітні методики вирішення таких систем. Найчастіше це прості рівняння, що складаються із двох невідомих, тому будь-який існуючий метод для пошуку відповіді на них не триватиме багато часу. Це може бути метод підстановки, коли з одного рівняння виводиться інше і підставляється в початкове. Або метод почленного віднімання та додавання. Але найлегшим та універсальним вважається метод Гауса. Він дозволяє вирішувати рівняння з будь-якою кількістю невідомих. Чому саме ця методика вважається раціональною? Все просто. Матричний спосіб хороший тим, що тут не потрібно кілька разів переписувати непотрібні символи у вигляді невідомих, достатньо зробити арифметичні операціїнад коефіцієнтами - і вийде достатньо правильний результат.

Де використовуються СЛАУ на практиці

Рішенням СЛАУ є точки перетину прямих графіків функцій. У наш високотехнологічний комп'ютерний вік людям, які тісно пов'язані з розробкою ігор та інших програм, необхідно знати, як вирішувати такі системи, що вони представляють і як перевірити правильність результату. Найчастіше програмісти розробляють спеціальні програми-обчислювачі лінійної алгебри, сюди входить і система лінійних рівнянь. Метод Гауса дозволяє вирахувати всі існуючі рішення. Також використовуються й інші спрощені формули та методики.

Критерій сумісності СЛАУ

Таку систему можна вирішити лише у тому випадку, якщо вона сумісна. Для зрозумілості представимо СЛАУ як Ax=b. Вона має рішення, якщо rang(A) дорівнює rang(A,b). І тут (A,b) - це матриця розширеного виду, яку можна одержати з матриці А, переписавши її з вільними членами. Виходить, що розв'язати лінійні рівняння методом Гауса досить легко.

Можливо, деякі позначення не зовсім зрозумілі, тому треба розглянути все на прикладі. Допустимо, є система: x + y = 1; 2x-3y = 6. Вона складається з двох рівнянь, у яких 2 невідомі. Система матиме рішення тільки в тому випадку, якщо ранг її матриці дорівнюватиме рангу розширеної матриці. Що таке ранг? Це число незалежних рядків системи. У нашому випадку ранг матриці 2. Матриця А складатиметься з коефіцієнтів, що знаходяться біля невідомих, а в розширену матрицю вписуються і коефіцієнти, що перебувають за знаком «=».

Чому СЛАУ можна уявити в матричному вигляді

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

Перетворення матриць

Перш ніж переходити до рішення матриць, необхідно знати, які дії можна проводити над їх елементами. Існує кілька елементарних перетворень:

• Переписуючи систему в матричний вигляд і здійснюючи її рішення, можна множити всі елементи ряду на той самий коефіцієнт.
• Для того щоб перетворити матрицю на канонічний вигляд, можна міняти місцями два паралельні ряди. Канонічний вигляд має на увазі, що всі елементи матриці, які розташовані по головній діагоналі, стають одиницями, а решта - нулями.
• Відповідні елементи паралельних рядів матриці можна додавати один до одного.

Метод Жордана-Гаусса

Суть розв'язання систем лінійних однорідних і неоднорідних рівнянь методом Гауса у тому, щоб поступово виключити невідомі. Припустимо, у нас є система із двох рівнянь, у яких дві невідомі. Щоб їх знайти, необхідно перевірити систему на сумісність. Рівняння методом Гауса вирішується дуже просто. Необхідно виписати коефіцієнти, що знаходяться біля кожного невідомого у матричний вигляд. Для вирішення системи потрібно виписати розширену матрицю. Якщо одне з рівнянь містить меншу кількість невідомих, тоді місце пропущеного елемента необхідно поставити «0». До матриці застосовуються всі відомі методи перетворення: множення, розподіл на число, додавання відповідних елементів рядів один до одного та інші. Виходить, що у кожному ряду потрібно залишити одну змінну зі значенням «1», інші призвести до нульового вигляду. Для більш точного розуміння слід розглянути метод Гаусса на прикладах.

Простий приклад вирішення системи 2х2

Для початку візьмемо просту систему алгебраїчних рівнянь, в якій буде 2 невідомих.

Перепишемо її у розширену матрицю.

Щоб вирішити цю систему лінійних рівнянь, потрібно зробити лише дві операції. Нам необхідно привести матрицю до канонічного вигляду, щоби по головній діагоналі стояли одиниці. Так, переводячи з матричного виду назад у систему, ми отримаємо рівняння: 1x+0y=b1 і 0x+1y=b2, де b1 і b2 - відповіді, що вийшли в процесі рішення.

1. Перша дія при вирішенні розширеної матриці буде такою: перший ряд необхідно помножити на -7 і додати відповідно відповідні елементи до другого рядка, щоб позбавитися одного невідомого в другому рівнянні.
2. Оскільки рішення рівнянь методом Гауса передбачає приведення матриці до канонічного виду, тоді необхідно і з першим рівнянням зробити ті ж операції і прибрати другу змінну. Для цього другий рядок віднімаємо від першого та отримуємо необхідну відповідь – рішення СЛАУ. Або, як показано на малюнку, другий рядок множимо на коефіцієнт -1 і додаємо до першого рядка елементи другого ряду. Це одне і теж.

Як бачимо, нашу систему вирішено методом Жордана-Гаусса. Переписуємо її у необхідну форму: x=-5, y=7.

Приклад рішення СЛАУ 3х3

Припустимо, що у нас є складніша система лінійних рівнянь. Метод Гауса дає можливість вирахувати відповідь навіть для самої, здавалося б, заплутаної системи. Тому, щоб глибше вникнути в методику розрахунку, можна переходити до складнішого прикладу з трьома невідомими.

Як і в колишньому прикладі, переписуємо систему у вигляді розширеної матриці і починаємо приводити її до канонічного вигляду.

Для вирішення цієї системи знадобиться зробити набагато більше дій, ніж у попередньому прикладі.

1. Спочатку потрібно створити в першому стовпці один одиничний елемент та інші нулі. Для цього множимо перше рівняння на -1 і додаємо до нього друге рівняння. Важливо запам'ятати, що перший рядок ми переписуємо у первісному вигляді, а другий - вже зміненому.
2. Далі прибираємо цю саму першу невідому з третього рівняння. Для цього елементи першого рядка множимо на -2 і додаємо їх до третього ряду. Тепер перший і другий рядки переписуються у первісному вигляді, а третій - вже із змінами. Як бачимо за результатом, ми отримали першу одиницю на початку головної діагоналі матриці та інші нулі. Ще кілька дій і система рівнянь методом Гауса буде достовірно вирішена.
3. Тепер необхідно виконати операції над іншими елементами рядів. Третя і четверта дія можна об'єднати в одну. Потрібно розділити другий і третій рядок на -1, щоб позбавитися від мінусових одиниць по діагоналі. Третій рядок ми вже привели до необхідного вигляду.
4. Далі наведемо до канонічного вигляду другий рядок. Для цього елементи третього ряду множимо на -3 і додаємо їх до другого рядка матриці. З результату видно, що другий рядок теж наведено до необхідної форми. Залишилося зробити ще кілька операцій та прибрати коефіцієнти невідомих із першого рядка.
5. Щоб з другого елемента рядка зробити 0, необхідно помножити третій рядок -3 і додати його до першого ряду.
6. Наступним вирішальним етапом буде додавання до першого рядка необхідні елементи другого ряду. Так ми отримуємо канонічний вид матриці, а відповідно і відповідь.

Як видно, розв'язання рівнянь методом Гауса досить просте.

Приклад розв'язання системи рівнянь 4х4

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

Нижче описано покрокова інструкціярішення такого прикладу.

У першій дії в порожні комірки вписуються вільні коефіцієнти та числа при невідомих. Таким чином, виходить така сама розширена матриця, яку ми пишемо вручну.

І виконуються всі необхідні арифметичні операції, щоб привести розширену матрицю до канонічного вигляду. Необхідно розуміти, що не завжди відповідь на систему рівнянь – це цілі числа. Іноді рішення може бути із дробових чисел.

Перевірка правильності рішення

Метод Жордана-Гаусса передбачає перевірку правильності результату. Для того щоб дізнатися, чи правильно пораховані коефіцієнти, необхідно всього лише підставити результат у початкову систему рівнянь. Ліва сторона рівняння має відповідати правій стороні, що знаходиться за знаком "рівно". Якщо відповіді не збігаються, тоді необхідно перераховувати заново систему або спробувати застосувати до неї інший відомий вам метод рішення СЛАУ, такий як підстановка або почленное віднімання та додавання. Адже математика – це наука, яка має величезну кількість різних методик розв'язання. Але пам'ятайте: результат повинен бути завжди той самий, незалежно від того, який метод рішення ви використовували.

Метод Гауса: найпоширеніші помилки при вирішенні СЛАУ

Під час розв'язання лінійних систем рівнянь найчастіше виникають такі помилки, як неправильне перенесення коефіцієнтів у матричний вигляд. Бувають системи, в яких відсутні в одному з рівнянь деякі невідомі, тоді переносячи дані в розширену матрицю, їх можна втратити. У результаті під час вирішення цієї системи результат може відповідати дійсному.

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

Метод Гаусса докладно визначає рішення лінійних рівнянь. Завдяки йому легко зробити необхідні операції та знайти правильний результат. Крім того, це універсальний засіб для пошуку достовірної відповіді на рівняння будь-якої складності. Можливо, тому його часто використовують при вирішенні СЛАУ.

Пояснювальна записка

Дана методична розробкапризначена щодо заняття з дисципліни “Математика” на тему “Рішення систем лінійних рівнянь методом Гаусса” за програмою навчальної дисципліни, розробленої з урахуванням Федерального державного освітнього стандарту для спеціальностей середньої професійної освіти.

Внаслідок вивчення теми студент повинен:

знати:

• елементарні перетворення над матрицями;
• етапи розв'язання систем лінійних рівнянь методом Гаусса

вміти:

• розв'язувати системи лінійних рівнянь методом Гаусса.

Цілі заняття:

навчальні:

• розглянути елементарні перетворення над матрицями;
• розглянути метод Гаусса на вирішення систем лінійних рівнянь.

розвиваючі:

• розвивати вміння аналізувати отриману інформацію, робити висновки;

виховні:

• виховувати у студентів інтерес до дисципліни, що вивчається, показувати значимість знань з даної теми для їх подальшої професійної діяльності;
• виховувати готовність та здатність до освіти, у тому числі самоосвіти, протягом усього життя.

Хід заняття

Оцінка "відмінно":

• робота виконана повністю;

Оцінка "добре":

Оцінка "задовільно":

Оцінка "незадовільно":

Загальний час- 90 хв.

План заняття:

1. Організаційний момент;
2. Перевірка позааудиторної самостійної роботи;
3. Теоретична частина;
4. Практична частина;
5. Підсумки заняття.

Теоретична частина

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

Система n лінійних рівнянь із m невідомими може мати вигляд:

I=1, 2, 3, …, n; j=1, 2, 3,..., m.

Зауважимо, що кількість невідомих m і кількість рівнянь n у випадку між собою ніяк не пов'язані. Можливі три випадки: m=n, m > n, m< n.

Рішенням системи називається будь-яка кінцева послідовність з m чисел ( , Що є рішенням кожного з рівнянь системи.

Процес рішення за методом Гауса складається із двох етапів:

1. Система наводиться до ступінчастого (трикутного) виду

2. Послідовне визначення невідомих із ступеневої системи, що вийшла.

Нехай дана система трьох лінійних рівнянь із трьома невідомими x, y, z

Введемо на розгляд матрицю систему і розширену матрицю .

Елементарні перетворення матриць:

1. Перестановка місцями двох рядів матриці:

;

2. Множення (розподіл) всіх елементів ряду матриці на число, відмінне від нуля:

Розділимо елементи першого рядка на 2, а другий – помножимо на 2

.

3. Додаток до всіх елементів одного ряду матриці відповідних елементів іншого ряду, помножених на те саме число:

Помножимо елементи першого рядка на 2:

.

Додамо до всіх елементів першого рядка відповідні елементи другого рядка, при цьому елементи першого рядка запишемо без змін:

Розділимо елементи першого рядка на 2:

Насправді деякі дії виконують усно:

Якщо в процесі перетворення з'явиться нульовий ряд у матриці, його можна видалити.

Розглянемо суть методу Гауса на конкретній системі лінійних рівнянь (див. додаток):

Розв'яжіть систему лінійних рівнянь методом Гауса

Запишемо розширену матрицю:

Вихідна система звелася до ступінчастої:

З останнього рівняння з передостаннього рівняння або .

Знайдемо з першого рівняння: або.

г)

Критерії оцінки виконання самостійної роботи:

Оцінка "відмінно":

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

Оцінка "добре":

• робота виконана повністю, але обґрунтування кроків рішення недостатні (якщо вміння обґрунтовувати міркування не було спеціальним об'єктом перевірки);
• допущено одну помилку або є два-три недоліки у викладках, малюнках, кресленнях або графіках (якщо ці види робіт не були спеціальним об'єктом перевірки).

Оцінка "задовільно":

• допущено більше однієї помилки або більше двох-трьох недоліків у викладках, кресленнях або графіках, але той, хто навчається, має обов'язкові вміння по темі, що перевіряється.

Оцінка "незадовільно":

• допущені суттєві помилки, які показали, що той, хто навчається, не має обов'язкових вмінь на цю тему повною мірою.

Дана система лінійних рівнянь алгебри (СЛАУ) з невідомими. Потрібно вирішити цю систему: визначити, скільки рішень вона має (жоден, одне або нескінченно багато), а якщо вона має хоча б одне рішення, то знайти будь-яке з них.

Формальнозавдання ставиться так: розв'язати систему:

де коефіцієнти та відомі, а змінні - Шукані невідомі.

Зручне матричне подання цього завдання:

де - матриця, складена з коефіцієнтів, і - Вектори-стовпці висоти.

СЛАУ може бути не над полем дійсних чисел, а над полем за модулембудь-якого числа , тобто:

— алгоритм Гауса працює і для таких систем теж (але цей випадок буде розглянуто нижче в окремому розділі).

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

Строго кажучи, описаний нижче метод правильно називати методом "Гаусса-Жордана" (Gauss-Jordan elimination), оскільки він є варіацією методу Гаусса, описаної геодезистом Вільгельмом Жорданом в 1887 р. (Варто відзначити, що Вільгельм Жордан не є автором ні теореми кривих, ні жорданової алгебри — все це три різних вчених-однофамільця; Також цікаво помітити, що одночасно з Жорданом (а за деякими даними навіть раніше за нього) цей алгоритм придумав Класен (B.-I. Clasen).

Базова схема

Коротко кажучи, алгоритм полягає в послідовному виключеннізмінних із кожного рівняння до того часу, поки кожному рівнянні залишиться лише з однієї змінної. Якщо , то можна говорити, що алгоритм Гаусса-Жордана прагне привести матрицю системи до одиничної матриці - адже після того як матриця стала одиничною, рішення системи очевидно - рішення єдине і задається коефіцієнтами.

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

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

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

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

Пошук опорного елемента (pivoting)

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

Щоб зробити алгоритм працюючим у таких випадках, якраз і існує процес вибору опорного елемента(на англійськоюце називається одним словом "pivoting"). Він полягає в тому, що проводиться перестановка рядків та/або стовпців матриці, щоб у потрібному елементівиявилося ненульове число.

Зауважимо, що перестановка рядків значно простіше реалізується на комп'ютері, ніж перестановка стовпців: адже при обміні місцями двох якихось стовпців треба запам'ятати, що ці дві змінні обмінялися місцями, щоб потім при відновленні відповіді правильно відновити, яка відповідь до якої змінної відноситься . При перестановці рядків жодних додаткових дій робити не треба.

На щастя, для коректності методу достатньо лише обмінів рядків (т.зв. "partial pivoting", на відміну від "full pivoting", коли обмінюються і рядки, і стовпці). Але який саме рядок слід обирати для обміну? Чи правда, що пошук опорного елемента треба робити тільки тоді, коли поточний елемент нульовий?

Спільної відповіді це питання немає. Є різноманітні евристики, проте найефективнішою з них (за співвідношенням простоти та віддачі) є така евристика: як опорний елемент слід брати найбільший за модулем елемент, причому здійснювати пошук опорного елемента і обмін з ним треба завждиа не тільки коли це необхідно (тобто не тільки тоді, коли ).

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

По-перше, ця евристика дозволить вирішити СЛАУ, навіть якщо по ходу рішення траплятиметься так, що елемент . По-друге, що дуже важливо, ця евристика покращує чисельну стійкістьалгоритм Гаусса-Жордана.

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

Вироджені випадки

Отже, якщо зупинятися на алгоритмі Гауса-Жордана з partial pivoting, то, стверджується, якщо й система невироджена (тобто має ненульовий визначник, що означає, що вона має єдине рішення), то описаний вище алгоритм повністю відпрацює та прийде до одиничної матриці (доказ цього, тобто того, що ненульовий опорний елемент завжди перебуватиме, тут не наводиться).

Розглянемо тепер загальний випадокколи і не обов'язково рівні. Припустимо, що опорний елемент на -ом кроці не знайшовся. Це означає, що в стовпці всі рядки, починаючи з поточної, містять нулі. Стверджується, що в цьому випадку ця змінна не може бути визначена, і є незалежної змінної(може набувати довільного значення). Щоб алгоритм Гаусса-Жордана продовжив свою роботу для всіх наступних змінних, у такій ситуації треба просто пропустити поточний стовпець, не збільшуючи при цьому номер поточного рядка (можна сказати, що ми віртуально видаляємо стовпець матриці).

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

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

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

Реалізація

Наведемо тут реалізацію алгоритму Гаусса-Жордана з евристикою partial pivoting (вибір опорного елемента як максимуму по стовпцю).

На вхід функції передається сама матриця системи. Останній стовпець матриці - це в наших старих позначеннях стовпець вільних коефіцієнтів (так зроблено для зручності програмування - тому що в самому алгоритмі всі операції з вільними коефіцієнтами повторюють операції з матрицею).

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

EPS) return 0;

) for (int i = 0; i

У функції підтримуються два вказівники - на поточний стовпець і поточний рядок .

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

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

Асимптотика

Оцінимо асимптотику отриманого алгоритму. Алгоритм складається з фаз, кожної з яких відбувається:

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

Таким чином, підсумкова асимптотикаалгоритму набуває вигляду.

При цьому оцінка перетворюється на .

Зауважимо, що коли СЛАУ розглядається не в полі дійсних чисел, а в полі за модулем два, то систему можна вирішувати набагато швидше - про це див. нижче в розділі "Рішення СЛАУ за модулем".

Точніша оцінка числа дій

Як ми знаємо, час роботи всього алгоритму фактично визначається часом, що витрачається на виключення поточного рівняння з інших.

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

Додатки

Прискорення алгоритму: поділ його на прямий та зворотний хід

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

Загалом, на відміну від описаного вище алгоритму, можна наводити матрицю не до діагонального вигляду, а до трикутного виглядуколи всі елементи строго нижче головної діагоналі дорівнюють нулю.

Система з трикутною матрицею вирішується тривіально - спочатку з останнього рівняння відразу знаходиться значення останньої змінної, потім знайдене значення підставляється в передостаннє рівняння і значення передостанньої змінної, і так далі. Цей процес і називається зворотним ходомалгоритм Гауса.

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

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

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

Рішення СЛАУ за модулем

Для вирішення СЛАУ за модулем можна застосовувати описаний вище алгоритм він зберігає свою коректність.

Зрозуміло, тепер стає непотрібним використовувати якісь хитрі техніки вибору опорного елемента - достатньо знайти будь-який ненульовий елемент у стовпці.

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

Особливо чудовий модуль, рівний двом: для нього всі операції з матрицею можна робити дуже ефективно Наприклад, віднімання одного рядка від іншого за модулем два - це насправді їхня симетрична різниця ("xor"). Таким чином, весь алгоритм можна значно прискорити, стиснувши всю матрицю в бітові маски та оперуючи лише ними. Наведемо нову реалізацію основної частини алгоритму Гаусса-Жордана, використовуючи стандартний контейнер C++ "bitset":

for (int col = 0, row = 0; col

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

(Не обов'язково простий), то все стає дещо складніше. Зрозуміло, що користуючись китайською теоремою про залишки, ми зводимо завдання з довільним модулем тільки до модулів виду "ступінь простого". [ Подальший текст був прихований, т.к. це неперевірена інформація - можливо, неправильний спосіб вирішення Зрештою, розглянемо питання. Відповідь на нього досить проста: число рішень дорівнює , де модуль, — число незалежних змінних.

Трохи про різні способи вибору опорного елемента

Як уже говорилося вище, однозначної відповіді це питання немає.

Евристика "partial pivoting", яка полягала у пошуку максимального елемента в поточному стовпці, працює на практиці дуже непогано. Також виявляється, що вона дає практично той же результат, що і full pivoting - коли опорний елемент шукається серед елементів цілої підматриці - починаючи з поточного рядка і з поточного стовпця.

Але цікаво відзначити, що обидві ці евристики з пошуком максимального елемента фактично дуже залежать від того, наскільки були промасштабовані вихідні рівняння. Наприклад, якщо одне з рівнянь системи помножити на мільйон, це рівняння майже напевно буде обрано як ведучого першому кроці. Це здається досить дивним, тому логічним є перехід до трохи складнішої евристики — так званого "implicit pivoting".

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

Поліпшення знайденої відповіді

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

У зв'язку з цим, отриману алгоритмом Гаусса-Жордана відповідь можна поліпшити, застосувавши до нього будь-який простий чисельний метод, наприклад, метод простої ітерації.

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

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

Література

• William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. Numerical Recipes: The Art of Scientific Computing
• Anthony Ralston, Philip Rabinowitz. A first course in numerical analysis

Сьогодні розбираємося з методом Гауса для вирішення систем лінійних рівнянь алгебри. Про те, що це за системи, можна почитати у попередній статті, присвяченій рішенню тих самих СЛАУ методом Крамера. Метод Гауса не вимагає якихось специфічних знань, потрібна лише уважність та послідовність. Незважаючи на те, що з точки зору математики для його застосування вистачить і шкільної підготовки, у студентів освоєння цього методу часто викликає труднощі. У цій статті спробуємо звести їх нанівець!

Метод Гауса

М етод Гауса- Найбільш універсальний метод рішення СЛАУ (за винятком дуже великих систем). На відміну від розглянутого раніше, він підходить не тільки для систем, що мають єдине рішення, але і для систем, у яких рішень безліч. Тут можливі три варіанти.

1. Система має єдине рішення (визначник головної матриці системи не дорівнює нулю);
2. Система має безліч рішень;
3. Рішень немає, система несумісна.

Отже, ми маємо систему (нехай у неї буде одне рішення), і ми збираємося вирішувати її методом Гауса. Як це працює?

Метод Гауса складається з двох етапів – прямого та зворотного.

Прямий хід методу Гауса

Спочатку запишемо розширену матрицю системи. Для цього до головної матриці додаємо стовпець вільних членів.

Вся суть методу Гауса полягає в тому, щоб шляхом елементарних перетворень привести цю матрицю до ступінчастого (або як ще кажуть трикутного) вигляду. У такому вигляді під (або над) головною діагоналлю матриці мають бути одні нулі.

Що можна робити?

1. Можна переставляти рядки матриці місцями;
2. Якщо у матриці є однакові (або пропорційні) рядки, можна видалити їх усі, крім одного;
3. Можна множити чи ділити рядок на будь-яке число (крім нуля);
4. Нульові рядки видаляються;
5. Можна додавати до рядка рядок, помножений на число, відмінне від нуля.

Зворотний хід методу Гауса

Після того як ми перетворимо систему таким чином, одна невідома Xn стає відома, і можна в зворотному порядку знайти всі невідомі, підставляючи вже відомі ікси в рівняння системи, аж до першого.

Коли інтернет завжди під рукою, можна вирішити систему рівнянь методом Гаусса онлайн.Достатньо лише вбити в онлайн-калькулятор коефіцієнти. Але погодьтеся, набагато приємніше усвідомлювати, що приклад вирішено не комп'ютерною програмою, а Вашим власним мозком.

Приклад розв'язання системи рівнянь методом Гаусс

А тепер – приклад, щоб усе стало наочно та зрозуміло. Нехай дана система лінійних рівнянь і потрібно вирішити її методом Гауса:

Спочатку запишемо розширену матрицю:

Тепер займемося перетвореннями. Пам'ятаємо, що нам потрібно досягти трикутного вигляду матриці. Помножимо 1-ий рядок на (3). Помножимо 2-й рядок на (-1). Додамо 2-й рядок до 1-го і отримаємо:

Потім помножимо 3-й рядок на (-1). Додамо 3-й рядок до 2-го:

Помножимо 1-ий рядок на (6). Помножимо 2-й рядок на (13). Додамо 2-й рядок до 1-го:

Вуаля – система приведена до відповідного виду. Залишилось знайти невідомі:

Система у цьому прикладі має єдине рішення. Вирішення систем з безліччю рішень ми розглянемо в окремій статті. Можливо, спочатку Ви не знатимете, з чого почати перетворення матриці, але після відповідної практики наб'єте руку і клацатимете СЛАУ методом Гауса як горішки. А якщо Ви раптом зіткнетеся зі СЛАУ, яка виявиться надто міцним горішком, звертайтеся до наших авторів! ви можете, залишивши заявку у Заочнику. Разом ми вирішимо будь-яке завдання!