1. Матеріал з MachineLearning. Постановка задачі
2. опис методу
3. аналіз методу
4. Способи оцінки помилок
5. Поліпшення методу виключення Гауса
6. Вибір головного елемента
7. Итеративное поліпшення результату
8. числовий приклад
9. Програма, що реалізує метод на C ++
10. рекомендації користувачеві

Матеріал з MachineLearning.

Постановка задачі

дана система лінійних алгебраїчних рівнянь (СЛАР), що складається з рівнянь з невідомими:

(1)

Передбачається, що існує єдине рішення системи, тобто .

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

опис методу

Процес рішення системи лінійних рівнянь

(2)

за методом Гаусса складається з 2-х етапів:

• Прямий хід Система (2) приводиться до трикутного вигляду

1. Припускаємо, що . Тоді перше рівняння системи (2) ділимо на коефіцієнт , В результаті отримуємо рівняння . Потім з кожного з решти рівнянь віднімається найперше, помножене на відповідний коефіцієнт . В результаті система перетворюються до вигляду: 2. У припущенні, що , Ділимо друге рівняння на коефіцієнт і виключаємо невідоме з усіх наступних рівнянь і т.д. 3. Отримуємо систему рівнянь з трикутною матрицею:

(3)

• Зворотний хід Безпосереднє визначення невідомих

1. З го рівняння системи (3) визначаємо 2. З го - визначаємо і т.д.

аналіз методу

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

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

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

Можливі 3 випадки:

1) :

2) :

3) :

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

Проілюструємо отримані результати на наступному числовому прикладі: Дана система

Вона має рішення .

Тепер розглянемо обурену систему:

Рішенням такої системи буде вектор .

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

Такий результат можна було передбачити в силу поганої обумовленістю матриці : [1]

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

Способи оцінки помилок

1) Контрольна сума: зазвичай застосовується для попередження випадкових похибок в процесі обчислення без допомоги комп'ютерів.

Складаємо контрольний стовпець , Що складається з контрольних елементів системи:

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

2) Відносна похибка відомого рішення дозволяє без істотних додаткових витрат отримати судження про похибки рішення.

Здається деякий ветор з компонентами, які мають по можливості той же порядок і знак, що і компоненти шуканого рішення [1] . обчислюється вектор , І на ряду з вихідною системою рівняння вирішується система .

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

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

Поряд з вихідною системою тим же методом вирішується система

, де і - числа

Якби не було похибки округлення, то виконувалося б рівність для рішень вихідної і масштабированной систем: . Тому при і , Які не є ступенями двійки, порівняння векторів і дає уявлення про величину обчислювальної похибки [1]

Поліпшення методу виключення Гауса

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

Вибір головного елемента

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

Нехай по ходу виключення невідомих отримана система рівнянь:

, .

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

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

Итеративное поліпшення результату

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

.

Вирішуючи цю систему, отримуємо наближення до і вважаємо

.

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

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

числовий приклад

Розглянемо для прикладу матрицю Вандермонда розміром 7х7 і 2 різні праві частини:

Дані системи були вирішені двома способами. Тип даних - float. B результаті отримали наступні результати:

Звичайний метод 1 2 1 2 1 2 0.999991 1 0.999996 1 1.00019 1 7.4774e-005 2,33e-008 0.998404 1 0.999375 1 1.00667 1 0.00263727 1,12e-006 0.985328 1 0.994149 1 1.01588 1 0.00637817 3,27e-006 0.993538 1 0.99739 1 0,045479 2,9826e-006 0,01818 8,8362e-006 0,006497 4,2608e-007 0,0045451 2,209e-006 0,040152 4,344e-005 0,083938 2,8654e-006 С вибором ведучого елемента по рядку 1 2 1 2 1 2 1 1 1 1 1 1 -3.57628e-005 1,836e-007 1.00001 1 1.00031 1 0.999942 1 -0.00133276 7,16e-006 1.00005 1 1.00302 0,99998 1.00009 1 -0.0033505 1,8e -005 0.99991 1 1.00139 0,99999 0,000298 4,3835e-007 0,009439 5,0683e-005 4,2571e-005 6,2622e-008 0,0023542 1,2671e-005 0,010622 9,8016e-007 0,29402 1,4768e-006 Реальні результатів від 1 до 2 - - 1 1 1 0 1 1 1 0 1 1 1 0 1 1 0 0 0 0 0 0

Програма, що реалізує метод на C ++

Gauss_Elimination.zip [30Кб] - В архіві міститься вихідний код, exe-файл і приклад файлу з вхідними даними

рекомендації користувачеві

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

• Ітераційне поліпшення результату варто провести 2-3 рази, якщо похибка зменшується дуже повільно - можливо, матриця погано обумовлена, тоді метод в будь-якому випадку дасть не найкращі результати - краще спробувати застосувати ітераційні методи.

• Важливо, щоб дані зчитувалися з файлу правильно.

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

• Є можливість змінювати точність обчислень (float і double), але в исходниках.

виноски

Список літератури

• Н.С.Бахвалов, Н.П.Жідков, Г.М.Кобельков Чисельні методи
• Д. Мак-Кракена, У.Дорн Чисельні методи та програмування на фортране
• JCNash Compact numerical methods for computers. Linear algebra anf function minimization. Second edition.
• Nicholas J.Higham How Accurate is Gaussian Elimination?

зовнішні посилання

Див. також