Форсайт Дж., Малькольм М., Моулер К. - Машинные методы математических вычислений (1040536), страница 10
Текст из файла (страница 10)
Ошибки округления, малые по отношению к этим большим коэффициентам, неприемлемы с точки зрения уровня элементов исходной матрицы и действительного решения. Предоставляем читателю проверить, что если второе и третье уравнения переставляются, то больших множителей не возникает и конечный результат будет удовлетворительным. Это оказывается верным и в общем случае: если множители не превосходят 1 по абсолютной величине, то можно показать, что вычисленное решение достаточно точно. Обеспечить, чтобы множители по модулю были не больше 1, можно посредством процесса, известного как частичный выбор ведущего элемента: на й-м шаге прямого хода в качестве ведущего берется наибольший (по абсолютной величине) элемент в неприведенной части й-го столбца, Строка, содержащая этот элемент, переставляется с А-й строкой с тем, чтобы перевести ведущий элемент в позицию (А, (е).
Такие же перестановки должны производиться с элементами правой части Ь. Неизвестные в векторе х не переупорядочиваются, поскольку столбцы в Л пе переставлялись. Если еще до начала исключения строка или столбец в А умножаются иа некоторый масштабирующнй множитель, то легко проделать компенсирующее изменение вычисленного решения. Подобные масштабирующие множители можно выбрать так, чтобы в процессе масштабирования не возникало ошибок округления, а тогда точное решение линейной системы не изменится. Однако масштабирование матрицы может полностью изменить выбор ведущих элементов и соответствующие перестановки и, следовательно, изменить точность вычисленного решения.
Обычная практика заключается в том, чтобы уравновесить матрицу ЗЛ. ЛИНЕЙНЫЕ СИСТЕМЫ С ХРАНИМЫМИ МАТРИЦАМИ 5! таким образом, что максимальные элементы каждой строки и каждого столбца будут примерно одной величины, Однако в этом процессе есть определенные трудности. Рассмотрим матрицу А=- 10' — 1 1 Деля первый столбец А на !0', получаем В=. 1 — 11 С другой стороны, деля последние две строки А на 1О', приходим к матрице В то время как обе матрицы уравновешены, В будет хорошо вести себя в алгоритме с выбором ведущего элемента, а С даст вырожденную матрицу на любой машине, работающей менее чем с девятью значащими десятичными цифрами. (Проверьте это.) Задачи этого типа обычно конструируются с целью иллюстрации и редко возникают на практике.
1(огда же такая ситуация действительно встречается, то задача нли алгоритм, производящий матрицу, должны быть проанализированы более тщательно, прежде чем решать линейную систему, Проблема построения гарантированного масштабирующего алгоритма пока еще не решена. Поэтому мы реши.пи принимать исходную матрицу такой, какая она есть, и не производить никакого масштабирования. Ошибки округлений, совершенных в процессе вычислений, почти всегда приводят к тому, что вычисленное решение (которое мы будем теперь обозначать через х„) в определенной степени отличается от теоретического решения х=А -'Ь.
В действительности оно н должно отличаться, поскольку компоненты вектора х обычно не являются числами с плавающей точкой. Имеются две общепринятые меры отклонения для х : ошибка е=-х — х, и невязка ') г=Ь вЂ” Ах,. ') В дальнейшем автори употребляют термнн «невязка» как для определенного здесь вектора, так н для его компонент.— Прнаь перев. х линеЙные системы уРАВнений Теория матриц говорит, что если одна из этих величин равна! нулю, то и другая также должна быть равна нулю, Но они не! обязаны одновременно быть «малымиъ.
Рассмотрим такой пример: (о.ово о.вову,,) (о.ло) Что случится, если провести гауссово исключение с частичным выбором на гипотетической трехзначной десятичной машине с, усечением? Прежде всего строки (уравнення) будут перестав. лены так, чтобы 0.913 стало ведущим элементом. Затем вычисляется множитель 0.780 — =0.854 (с тремя знаками). 0.9!3 Д алее новая первая строка, умноженная на 0.854, вычитается из новой второй строки, что приводит к системе 0.913 0.659 х, 0.254 Наконец, выполняется обратная подстановка 0.00! Ав — — 0 00! — — 1.00 (точный результат), !0.254 †.559х,! 0.9!З = — 0.443 (с тремя знаками). Итак, вычисленное решение есть — О.
443 Если бы мы ие знали правильного ответа, то с целью оценить полученную точность могли бы (точно) вычислить невязку: [ О. 217 — [(О. 780) ( — О. 443) + (О. 563) (1.00) ! '! 0.254 — [(0.91 3) ( — 0.443) + (0.659) (!.00) ! — 0.0004608 — 0.00054! ) Все нееязки меньше, чем 10-'. Едва лн можно ожидать лучшего на трехзначной машине. Однако легко видеть, что точное решение этой системы есть — 1. 000 Таким образом, ошибка больше, чем решение.
ЗЛ. ЛИНЕЙНЫЕ СИСТЕМЫ С ХРАНИМЫМИ МАТРИЦАМИ Я Были ли малые невязки счастливой случайиостьюр Прежде всего, читатель уже начал понимать к настоящему моменту, что приведенный пример в высшей степени искусствен. Матрица невероятно близка к вырожденной и не является типичной для большинства задач, встречаемых в практике. Тем не менее проследим причины малости невязок. Если гауссово исключение с частичным выбором выполнить для этого примера на машине с шестью или более разрядами, то прямой ход приведет к системе такого вида: (оюоооо о.ооиоо1(,) ( о.оооооо) Заметим, что знак Ьэ отличается от полученного при трехзначном вычислении.
Теперь обратная подстановка дает 0.254 †.659хе 1.00000 0.913 что совпадает с точным ответом. На нашей трехзначной машине х, было получено как частное двух величин, каждая из которых имела тот же порядок, что и ошибки округления, а одна не имела даже верного знака '). Следовательно, х, могло оказаться почти произвольным числом. (И действительно, если бы мы использовали машину с девятью двоичными разрядами, то получили бы совершенно другое значение.) Затем это вполне произвольное значение х, подставляется в первое уравнение для нахождения х,.
У нас есть все основания ожидать, что невязка первого уравнения будет мала: х, вычисляется таким образом, чтобы гаран« тировать это. Теперь мы подходим к тонкому, но очень важному пункту. Именно, можно также ожидать, что и невязка второго уравнения будет мала как раз потому, что матрица спюль близка к вырожденной. Каждое из двух уравнений почти кратно другому, так что любая пара (х„х,), которая почти удовлетворяет первому уравнению, будет в то же время почти удовлетворять второму.
Если бы матрица была в точности вырожденной, то второе уравнение нам вовсе не потребовалось бы — любое решение первого автоматически удовлетворяло бы второму. Хотя приведенный пример сконструирован и нетипичен, вывод, который мы из него сделали, таковым не является. Вероятно, это наиболее важный факт, который был установлен за прошедшие 15 или 20 лет людьми, связанными с матричными вычислениями: гауссово исключение с частичным выбором ведущего влеменпта гарантированно дает малые невязки. о) Имеется в виду эиэи числа, э ие эиэчащэя цифре.— Прил. иерее.
3. линейные системы уРАВнениЙ 54 Теперь, сформулировав это утверждение в столь сильной форме, сделаем пару уточняющих замечаний. Говоря <гаранти. роваино», мы подразумеваем, что можно доказать точную тео. рему, предполагающую некоторые технические детали относи. тельно аппаратной реализации плавающей арифметики и уста. навливающую определенные неравенства, которым должны удовлетворять компоненты невязки.
Если арифметическое устройствс работает каким-то иным образом или в данной программе имеется дефект, то, разумеется, «гарантия» отсутствует. Далее, под «малостью» мы имеем в виду порядок ошибок округления п« отношению к величинам следующих трех видов: элементау исходной матрицы коэффициентов, элементам матриц на про. межуточных шагах процесса исключения и компонентам вы.
численного решения. Если какие-либо из этих величин «боль. шие», то невязка не обязательно будет мала в абсолютном смысле. Наконец, даже если невязка мала, мы не станем делать отсюда вывода, что и ошибка мала. Связь между величиной невязки и величиной ошибки определяется отчасти характеристикой, называемой числом обусловленности матрицы, которое является предметом следующегс параграфа.
3.2. Обусловленность матрицы Коэффициенты матрицы и правой части системы линейных уравнений редко бывают известны точно. Некоторые системы возникают из эксперимента, и тогда коэффициенты подвержены ошибкам наблюдения. Коэффициенты других систел« записываются формулами, что влечет ошибки округлений при их вычислении. Даже если систему можно точно записать в память машины, в ходе ее решения почти неизбежно будут сделаны ошибки округлений. Можно показать, что ошибки округлений В гауссовом исключении имеют то же влияние на ответ, что и ошибки в исходных коэффициентах.
Вследствие этого мы подходим к фундаментальному вопросу. Если в коэффициентах системы линейных уравнений делаются ошибки, то как сильно при этом меняется решение? Или, другими словами, если Ах=-Ь, то как можно измерить чувствительность А по отношению к изменениям в А и Ь? Ответ на этот вопрос лежит в уточнении понятия «почв«и вырожденная».
Если А — вырожденная матрица, то для некоторых Ь решение х не существует, тогда как для других Ь оно будет неединственным. Таким образом, если А почти вырождена, то можно ожидать, что малые изменения в А и Ь вызовут очень большие изменения в х. С другой стороны, если А — единичная вл овисловленность млтиицы 55 матрица, то Ь и х — один и тот же вектор. Следовательно, если А близка к единичной матрице, то малые изменения в А и Ь должны влечь за собой соответственно малые изменения в х. На первый взгляд может показаться, что есть некоторая связь между величиной ведущих элементов в гауссовом исключении с частичным выбором и близостью к вырожденнссти, поскольку если бы арифметику можно было выполнять точно, то все ведущие элементы были бы отличны от нуля тогда и только тогда, когда матрица не вырождена.
До некоторой степени верно также, что если ведущие элементы малы, то матрица близки и вырожденной. Однако при наличии ошибок округления обратное уже неверно г) — матрица может быть близка к вырожденной даже если ии один из ведущих элементов не мал. Чтобы получить более точную и надежную меру близости к вырожденности, нам потребуется ввести понятие нормы вектора. Норма — это число, которое измеряет общий уровень элементов вектора.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
