История и методология прикладной математики. Русанов, Росляков (2004) (1185895), страница 22
Текст из файла (страница 22)
Главные результаты были получены, в Х1Х веке Гауссом, Кронекером, Сильвестром, Грассманом и другими. Было введено важное понятие ранга прямоугольной матрицы как максимального порядка отличного от нуля ее минора. Доказана теорема Кронекера-Каяели, дающая полный ответ о множестве решений произвольной системы гп линейньгх уравнений с п неизвестными. Ответ зависит от ранга матрицы коэффициентов и ранга расширенной матрицы (с дополнением столбца правых частей).
2. Перейдем теперь к краткому изложению развития методов решения системы линейных уравнений Прямое решение системы с п неизвестными с помощью формул Крамера требует 2п п! умножений и пг сложений. Кроме того, из-за знакопеременности в суммах произведений происходит сокращение знаков и значительная потеря точности. Поэтому. прямое использование правила Крамера при п > 4 практически ', нецелесообразно. Усилия математиков-вычислителей в Х1Х и ХХ веках были направлены на разработку более эффективных и точных методов решения.
В основе большинства из них лежит метод исключения в его модификации, предложенной Гауссом. Это так называемый метод исключения с выбором главного элемента. Суть его состоит в том, что на каждом последовательном шаге исключается то неизвестное из числа оставшихся, коэффициент прн котором мак- ' симален по модулю. Модификация этого метода, предложенная французским математиком Камилем Жорданом, позволяет после п шагов получить на месте матрицы исходной системы обратную матрицу с переставленными строками и столбцами. Перестановки зависят от положения главных элементов и запо- .
минаются в процессе вычислений. Метод Жордана был доволь- . но популярен в 50-60-ых годах прошлого века при использова- ' нии ЭВМ с ограниченной памятью и успешно применялся для обращения матриц до 50-го порядка. — 106— = (х~~хг - ° ° хп). о о е а Метод легко списать на простом, однако, достаточно общем примере.
Пусть А представлена каким-то образом в виде суммы двух матриц А = Лг + Лг, причем существует и легко вычисляется А г (например, когда А1 — треугольная матрица). Тогда система (11.1) эквивалентна следующей х=Ях+А Ь, где Я= — А~ Аг. -) — 1 Положим х+ =йх" +Лг Ь.
107— (11.2) Другие методы с фиксированным числом шагов более эфЬективные, чем прямой метод исключения, были развиты для матриц специального вида (симметрических, антисимметриче.ких, ортогональных и т. и.). С точки зрения теории матриц все методы исключения сводятся к разложению матрицы системы на произведение двух треугольных матриц, т. е. таких, у которых равны нулю все элементы, стоящие ниже (верхняя треугольная) или выше (нижняя треугольная) главной диагонали. Так как обращение треугольной матрицы очень просто, то эффективность метода сводится к эффективности указанного разбиения.
В самом деле, пусть матрица системы А представлена в виде -1 -1 -1 А = о'Ъ', где 1У и У вЂ” треугольные. Тогда А' = И о' к главная задача состоит в нахождении о' и У. Наиболее просто эта задача решается для так называемых трехдизгональных матриц, у которых отличны от нуля только элементы, стоящие па главной диагонали и на двух соседних с нею, сверху и снизу. Метод исключения для такой матрицы приводит к так называемому алгоритму прогонки„разработанному в 40-х годах ХХ-го века при решении краевых задач для обыкновенных дифференциальных уравнений. Методы, о которых шла речь, дают решение системы после заранее фиксированного и зависящего только от п числа шагов. Такие методы обычно называются прямыми.
Параллельно с ними развивались и итерационные методы решения линейных систем. Суть их заключается в том, что решение системы (11.1) получается в результате последовательных итераций, начиная с о некоторого заданного значения вектора переменных х Если последовательность яь сходится, то предел гь при й — + со есть решение системы. Оставляя пока в стороне условия сходимости итерационного процесса, отметим, что итерационные методы в ряде случаев оказываются более эффективными, чем прямые, позволяя получить решение с необходимой точностью при меньшем объеме вычислений.
Заметим, однако, что существующие в настоящее время многочисленные пакеты программ для решения задач линейной алгебры на ЭВМ и персональных компьютерах основаны в большинстве случаев на прямых методах. 3. После того, как в математику вошло понятие определителя, естественным образом возникло и математическое понятие матрицы.
Матрица как двухиндексная таблица элементов является обобщением понития вектора (строки или столбца), однако, имеет и более глубокий смысл. Рассмотрим две квадратные матрицы А и В, и пусть беГА и с1еГ — их определители (два числа). Если взять две линейных системы х = Ау, у = Вг и затем выразить х непосредственно через г, т. е. найти матрицу С такую, что х = Сг, то оказывается, что деГС = с1е1А с1еГВ. Закон образования С очень прост, и естественно было назвать С произведением матриц А и В: г = Ау = А . Вг, С = А . В.
Так, или подобно этому, возникла идея алгебры матриц. Понятие суммы матриц также было естественно определить исходя из формул г = Аг, у = Вг, х+у = (А+ В)г. Теория матриц развилась в самостоятельную болыпую ветвь алгебры и оказалась очень плодотворной. Нашей задачей не — 108— является исследование развития этой теории. Отметим, однако, один замечательный факт.
Вначале, ео второй половине Х1Х века, матрицы представлялись чисто математическим призуманным объектом, удобным для описания некоторых математических закономерностей, а теория матриц — - в некотором смысле — "игрой ума чистых математиков". А затем, на рубеже Х1Х н ХХ веков, вкруг оказалось, что в науках о мире и его закономерностях, прежде всего это относилось к физике и механике, существуют такие реальные объекты и соотношения межлу наблюдаемыми величинами, которые могут быть в полной мере поняты и описаны только с привлечением матричных понятий.
Одним из важнейших понятий теории матриц, тесно связан. ным с ее прикладными применениями, является понятие собственного вектора х и соответствующего ему собственного значения Л, удовлетворяющих системе Ах=Ля, гфО. Очевипно, что Л есть корень характеристическою уравнения с1е1(А — ЛЕ) ив з Х(Л) = О.
Так как Х(Л) есть многочлен степени и, то любая матрица имеет, с учетом кратности, и собственных значений. Собственных векторов может быть меньше и, но не менее одного. Совокупность собственных значений матрицы образуют ее спектр. Задача численного исследования спектральных свойств матриц, методы вычисления собственных значений и собственных векторов составляют проблему собственных значений. Это одна из важнейших проблем численного анализа. Вот как характеризует ее крупнейший специалист в этой области английский ученый Дж. Х. Уилкинсон в своем фундаментальном труде "Алгебраическая проблема собственных значений", вышедшем на русском языке в 1970 году.
"Проблема собственных значений имеет обманчиво простую формулировку, теоретическое обоснование ее известно в течение многих лет; в то же время определение точных решений представляет обширное многообразие нерешенных проблем". Основная трудность, с которой сталкивается вычислитель в задачах, связанных, вообще, с матрицами состоит внешне в том, — 109— )Л,( » )Лг! > (Лз) > ... Рассмотрим итерационный процесс х+ =-А— К 1 !!хк!) (11.3) хк где Ох() — некоторая норма.
Можно показать, что вектор— !И! будет сходитьсл к собственному вектору 91 с нормой единица, а вектор х + к вектору Л191. Этот метод может оказаться очень К+1 эффективным. Отметим, что итерационная формула (11.3) для нахождения собственного вектора похожа на формулу (11.2) для решения системы Ах = Ь. В этом случае условием сходнмости будет выполнение неравенства )(Щ < 1, или, точнее, условия (Ц~)) -+ 0 при /с -+ сю.
Последнее выполняется, если все собственные значения Я по модулю меньше единицы. Если известны некоторые сведения о структуре спектра матрицы А, то иногда, рассматривая вместо А некоторую функцию 1'(А), можно добиться того, чтобы собственные значения у(А) были более резко разделены, чем собственные значения А. Например, если (Л1( > )Лг( > (Лз( > ..., то может оказаться, 110— что при повышении порядка матрицы очень быстро растут по»' грешности результата.
'Гак, теоретически простейший метод вы' числения собственных значений пушм вычисления коэффициентов характеристического многочлена и нахождения его корней теряет эффективность уже при и > 4, а при и > 7 лей становится вовсе нереальным даже при расчетах с плавающей запятой и. 40 знаками в двоичной мантиссе (12 десятичных знаков). Уве-' личение длины мантиссы до 64 и даже до 123 знаков позволяет продвинуть границу до и Ы 10, но это уже предел.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
