Гаусови методи за елиминиране

Материал от MachineLearning.

Съдържание

Формулиране на проблема

Дадена е система от линейни алгебрични уравнения (SLAE), състояща се от уравнения с неизвестни:

Предполага се, че има само едно решение за системата, т.е. .

Тази статия ще разгледа причините за грешката, която възниква по време на решението на системата, използвайки метода на Гаус, начини за идентифициране и отстраняване (намаляване) на тази грешка.

Описание на метода

Процесът на решаване на система от линейни уравнения

според метода на Гаус се състои от 2 етапа:

• Системата с директен ход (2) е намалена до триъгълна форма

1. Предполагаме, че. След това разделяме първото уравнение на система (2) на коефициента, в резултат на което получаваме уравнението. След това от всяко от останалите уравнения се изважда първото, умножено по подходящия коефициент. В резултат на това системата се трансформира в следната форма: 2. Ако приемем, че разделяме второто уравнение на коефициента и изключваме неизвестното от всички следващи уравнения и т.н. 3. Получаваме система от уравнения с триъгълна матрица:

• Обратно директно определяне на неизвестни

1. От th-тото уравнение на система (3) определяме 2. От th-то уравнение определяме и т.н.

Анализ на метода

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

Условията, при които методът дава точно решение, на практика не са осъществими - неизбежни са както грешките на входните данни, така и грешките при закръгляването. Тогава възниква въпросът: доколко точно може да се получи решението с помощта на метода на Гаус, доколко правилен е методът? Нека определим стабилността на решението по отношение на входните параметри. Заедно с оригиналната система (1), помислете и за смутената система:

Нека се въведе някаква норма. - се нарича номер на условието на матрицата .

Има 3 възможни случая:

Номерът на условието на матрицата е винаги. Ако е голям (), тогава се казва, че матрицата е лошо обусловена. В този случай малки смущения от дясната страна на системата (1), причинени или от неточност при посочване на първоначалните данни, или причинени от грешки в изчисленията, оказват значително влияние върху решението на системата. Грубо казано, ако грешката на дясната страна, тогава грешката на решението ще бъде .

Нека илюстрираме получените резултати със следния цифров пример: Като се има предвид системата

Тя има решение .

Сега помислете за смутената система:

Решението на такава система е векторът .

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

---