На что влияет число обусловленности матрицы

Число обусловленности матрицы

Рассмотрим систему линейных уравнений

Если матрица A вырожденная, то для некоторых b решение x не существует, а для других b оно будет неединственным. Следовательно, если A почти вырожденная, то можно ожидать, что малые изменения в A и b вызовут очень большие изменения в x. Если же взять в качестве A единичную матрицу, то решение системы (1) будет x=b. Следовательно, если A близка к единичной матрице, то малые изменения в A и b должны влеч за собой малые изменения в x.

Рассмотрим это на численном примере

Для оченки обусловленности матрицы вычисляют число обусловленности матрицы (обозначается символом «cond»). Для вычисления числа обусловленности введем понятия нормы для векторов x. В качестве нормы возмем l-норму вектора:

Умножая вектор х на матрицу A приводит к новому вектору Ax, норма которого может слишком отличаться от нормы вектора x. Эта чувствительность матрицы A мы хотим измерять. Максимальное и минимальное изменение Ax при изменении можно задать следующими числами:

Отношение Q/q называется числом обусловленности матрицы A:

В системе (1) изменим b на Δb. Тогда имеем:

Из (1) и (7) следует A·Δx=Δb. Тогда, учитывая (4) и (5) получим следующие неравенства:

Следовательно при q≠0 имеем:

При относительном изменении правой части , относительная ошибка может составить .

Свойства числа обусловленности матрицы:

Следующий пример иллюстрирует понятие числа обусловленности матрицы. Рассмотрим систему линейных уравнений (1), где

Тогда решением системы линейных уравнений будет . Если же правую заменить на , решением системы будет . Обозначим Δb=b-b1 и Δx=x-x1. Тогда

Из (13) видно, что очень малое изменение в b, совершенно изменил решение x. Так как

Неравенство (15) показывает что матрица A плохо обусловлена, т.е. близка к вырожденности. С помощью экспериментальных вычислений мы обнаружили плохую обусловленность матрицы A. А как, на самом деле, вычислить число обусловленности матрицы. В выражении (4) Q называется нормой матрицы и ее можно вычислить с помощью следующего вырaжения:

Источник

На что влияет число обусловленности матрицы

Матричные операции линейной алгебры

Вычисление нормы и чисел обусловленности матрицы

Определитель и ранг матрицы

Определение нормы вектора

Определение ортонормированного базиса матрицы

Приведение матрицы к треугольной форме

Определение угла между двумя подпространствами

Вычисление следа матрицы

Вычисление собственных значений и сингулярных чисел

Приведение матриц к формам Шура и Хессенберга

Линейная алгебра — область, в которой наиболее часто используются векторы и матрицы. Наряду с операциями общего характера, рассмотренными выше, применятся функции, решающие наиболее характерные задачи линейной алгебры. Они и рассмотрены в данном уроке.

Вычисление нормы и чисел обусловленности матрицы

Для понимания всего нижеизложенного материала необходимо учесть, что нормы матриц в MATLAB отличаются от норм векторов.

Пусть А —матрица. Тогда n=norm(A) эквивалентно п=погп(А,2) и возвращает вторую норму, т. е. самое большое сингулярное число А. Функция n=norm(A, 1) возвращает первую норму, т. е. самую большую из сумм абсолютных значений элементов матрицы по столбцам. Норма неопределенности n=norm(A, inf) возвращает самую большую из сумм абсолютных значений элементов матрицы по рядам. Норма Фробениуса (Frobenius) norm(A, ‘fro’) = sqrt(sum(diag(A’A))).

Числа обусловленности матрицы определяют чувствительность решения системы линейных уравнений к погрешностям исходных данных. Следующие функции позволяют найти числа обусловленности матриц.

cond(X) — возвращает число обусловленности, основанное на второй норме, то есть отношение самого большого сингулярного числа X к самому малому. Значение cond(X), близкое к 1, указывает на хорошо обусловленную матрицу;

р=1 — число обусловленности матрицы, основанное на первой норме;

р=2 — число обусловленности матрицы, основанное на второй норме;

p= ‘fro’ — число обусловленности матрицы, основанное на норме Фробе-ниуса (Frobenius);

р=’inf’ — число обусловленности матрицы, основанное на норме неопределенности.

с = cond(X) — возвращает число обусловленности матрицы, основанное на второй норме.

condeig(A) — возвращает вектор чисел обусловленности для собственных значений А. Эти числа обусловленности — обратные величины косинусов углов между левыми и правыми собственными векторами;

[V.D.s] = condeig(A) — эквивалентно [V,D] = eig(A): s = condeig(A);.

Большие числа обусловленности означают, что матрица А близка к матрице с кратными собственными значениями.

rcond(A) — возвращает обратную величину обусловленности матрицы А по первой норме, используя оценивающий обусловленность метод LAPACK. Если А — хорошо обусловленная матрица, то rcond(A) около 1.00, если плохо обусловленная, то около 0.00. По сравнению с cond функция rcond реализует более эффективный в плане затрат машинного времени, но менее достоверный метод оценки обусловленности матрицы.

Определитель и ранг матрицы

Для нахождения определителя (детерминанта) и ранга матриц в MATLAB имеются следующие функции:

det(X) — возвращает определитель квадратной матрицы X. Если X содержит только целые элементы, то результат — тоже целое число. Использование det(X)=0 как теста на вырожденность матрицы действительно только для матрицы малого порядка с целыми элементами.

-29
Детерминант матрицы вычисляется на основе треугольного разложения методом исключения Гаусса:

[L.U>lu(A): s=det(L): d=s*prod(diag(U)).

Ранг матрицы определяется количеством сингулярных чисел, превышающих порог

При этом используется следующий алгоритм:

Для вычисления ранга используется функция rank:

rank (А) — возвращает количество сингулярных чисел, которые являются большими, чем заданный по умолчанию допуск;

rank(A.tol) — возвращает количество сингулярных чисел, которые превышают tol. Пример:

Определение нормы вектора

Норма вектора — скаляр, дающий представление о величине элементов вектора. Нужно различать норму матрицы и норму вектора. Функция norm определяет, является ли ее аргументом (входным аргументом в терминологии MATLAB) вектор или матрица, и измеряет несколько различных типов норм векторов:

norm(X)=norm(X,2) — вторая норма возвращает наибольшее сингулярное число X, max(svd(X));

norm(X, ‘inf’) возвращает максимальное из абсолютных значений элементов вектора; О norm(X, ‘-Inf’) возвращает минимальное из абсолютных значений элементов вектора.

Определение ортонормированного базиса матрицы

Вычисление ортонормированного базиса матрицы обеспечивают нижеприведенные функции:

В = orth(A) — возвращает ортонормированный базис матрицы А. Столбцы В определяют то же пространство, что и столбцы матрицы А, но столбцы В ортогональны, то есть B*B=eye(rank(A)). Количество столбцов матрицы В равно рангу матрицы А.

» А=[2 4 6:9 8 2:12 23 43]

null (А) — возвращает ортонормированный базис для нулевого (пустого) пространства А.

Функции приведения матрицы к треугольной форме

Треугольной называется квадратная матрица А, если при l>k (верхняя треугольная матрица) или при к>1(нижняя треугольная матрица) элементы матрицы A(l,k) равны нулю. В строго треугольной матрице нули находятся и на главной диагонали. В линейной алгебре часто используется приведение матриц к той или иной треугольной форме. Оно реализуется следующими функциями:

rref (A) — возвращает приведенную к треугольной форме матрицу, используя метод исключения Гаусса с частичным выбором ведущего элемента. По умолчанию принимается значение порога допустимости для незначительного элемента столбца, равное (max(s1ze(A))*eps*norm(A,inf));

[R, jb] = rref (A) — также возвращает вектор jb, так что:

r = length (jb) может служить оценкой ранга матрицы А;

х( jb) — связанные переменные в системе линейных уравнений вида Ах=b;

А(:, jb) — базис матрицы А;

R(l:r.jb) — единичная матрица размера rхr;

[R. jb] = rref (A,to!) — осуществляет приведение матрицы к треугольной форме, используя метод исключения Гаусса с частичным выбором ведущего элемента для заданного значения порога допустимости tol;

rrefmovie(A) — показывает пошаговое исполнение процедуры приведения матрицы к треугольной.

Определение угла между двумя подпространствами

Угол между двумя подпространствами вычисляет функция subsрасе:

theta = subspace(A.B) — возвращает угол между двумя подпространствами, натянутыми на столбцы матриц А и В. Если А и В — векторы-столбцы единичной длины, то угол вычисляется по формуле acos(A’*B). Если некоторый физический эксперимент описывается массивом А, а вторая реализация этого эксперимента — массивом В, то subspace(A.B) измеряет количество новой информации, полученной из второго эксперимента и не связанной со случайными ошибками и флуктуациями.

» Н = hadamard(20);A = Н(:.2:4);В = Н(:.5:8):

Вычисление следа матрицы

След матрицы А — это сумма ее диагональных элементов. Он вычисляется функцией trace:

trace(A) — возвращает след матрицы. Пример:

Разложение Холецкого — известный прием матричных вычислений. Функция chol находит это разложение для действительных и комплексных эрмитовых матриц.

[R.p] = chol (X) с двумя выходными аргументами никогда не генерирует сообщение об ошибке в ходе выполнения разложения Холецкого квадратной матрицы X. Если верхняя треугольная часть и диагональ X задают положительно определенную матрицу, то р=0, a R совпадает с вышеописанным случаем, иначе р. — положительное целое число, a R — верхняя треугольная матрица порядка q=p-l, такая что R’*R=X(l:q,l:q).

Обращение матриц — функции inv, pinv

Обращение матриц — одна из наиболее распространенных операций матричного анализа. Обратной называют матрицу, получаемую в результате деления единичной матрицы Е на исходную матрицу X. Таким образом, Х^-1=Е/Х. Следующие функции обеспечивают реализацию данной операции:

inv(X) — возвращает матрицу, обратную квадратной матрице X. Предупреждающее сообщение выдается, если X плохо масштабирована или близка к вырожденной.

-2.04081.4228 1.5538 1.3730

На практике вычисление явной обратной матрицы не так уж необходимо. Чаще операцию обращения применяют при решении системы линейных уравнений вида Ах=b. Один из путей решения этой системы — вычисление x=inv(A)*b. Но лучшим с точки зрения минимизации времени расчета и повышения точности вычислений является использование оператора матричного деления х=А\b. Эта операция использует метод исключения Гаусса без явного формирования обратной матрицы.

В = pinv(A) — возвращает матрицу, псевдообратную матрице А (псевдообращение матрицы по Муру-Пенроузу). Результатом псевдообращения матрицы по Муру-Пенроузу является матрица В того же размера, что и А’, и удовлетворяющая условиям А*В*А=А и В*А*В=В. Вычисление основано на использовании функции svd(A) и приравнивании к нулю всех сингулярных чисел, меньших величины tol;

В = pinv (A. tol) — возвращает псевдообратную матрицу и отменяет заданный по умолчанию порог, равный max(size(A))*norm(A)*eps.

Так называемые LU- и QR-разложения реализуются следующими матричными функциями:

Функция 1и выражает любую квадратную матрицу X как произведение двух треугольных матриц, одна из которых (возможно, с перестановками) — нижняя тре угольная матрица, а другая — верхняя треугольная матрица[ В MATLAB 6 аргументом (входным аргументом) функции lu может быть и полная прямоугольная матрица. — Примеч. ред.]. Иногда эту операцию называют LR-разложением. Для выполнения этой операции служит следующая функция:

[L,U] = lu(X) — возвращает верхнюю треугольную матрицу U и психологическую нижнюю матрицу L (т. е. произведение нижней треугольной матрицы и матрицы перестановок), так что X=L*U;

[L,U,P.] = lu(X) — возвращает верхнюю треугольную матрицу U, нижнюю треугольную матрицу L и сопряженную (эрмитову) матрицу матрицы перестановок Р, так что L*U =Р*Х;

lu(Х) — вызванная с одним выходным параметром функция возвращает результат из подпрограмм DGETRF (для действительных матриц) или ZGETRF (для комплексных) известного пакета программ линейной алгебры LAPACK.

lu(X, thresh) — где thresh в диапазоне [0. 1] управляет центрированием в разреженных матрицах (см. урок 12). Отдельная форма предыдущего случая. Центрирование происходит, если элемент столбца на диагонали меньше, чем произведение thresh и любого поддиагонального элемента. Thresh=l — значение по умолчанию. Thresh=0 задает центрирование по диагонали. Если матрица полная (не разреженная), выводится сообщение об ошибке.

Функция qr выполняет QR-разложепие матрицы. Эта операция полезна для квадратных и треугольных матриц. Она выполняет QR-разложение, вычисляя произведение унитарной [Квадратная матрица с комплексными элементами, обладающая тем свойством, что обратная матрица ее комплексно сопряженной матрицы равна транспонированной, т. е. (А*)»-А’. — Примеч. ред.] матрицы и верхней треугольной матрицы. Функция используется в следующих формах: [ Квадратная матрица с комплексными элементами, обладающая тем свойством, что обратная матрица ее комплексно сопряженной матрицы равна транспонированной, т. е. (А*)»-А’. — Примеч. ред.]

[Q.R] = qr(X) — вычисляет верхнюю треугольную матрицу R того же размера, как и у X, и унитарную матрицу Q, так что X=Q*R;

[Q.R.E] = qr(X) — вычисляет матрицу перестановок Е, верхнюю треугольную матрицу R с убывающими по модулю диагональными элементами и унитарную матрицу Q, так что X*E=Q*R. Матрица перестановок Е выбрана так, что abs(diag(R)) уменьшается;

А = qr(X) — возвращает результат из LAPACK. Пример:

0.8381 0.5028 0.1934 0.6979

0.0196 0.7095 0.6822 0.3784

0.6813 0.4289 0.3028 0.8600

0.3795 0.3046 0.5417 0.8537

0.8318 0.1897 0.1509 0.5936

-0.4814-0.11730.0699 0.5940 0.6299

[Q,R] = qrdelete(Q,R, j) — изменяет Q и RTaKHM образом, чтобы пересчитать QR-разложение матрицы А для случая, когда в ней удален j-й столбец (А(:, j )=[ ]). Входные значения Q и R представляют QR-разложение матрицы А как результат действия [Q. R]=qr(A)..Аргумент j определяет столбец, который должен быть удален из матрицы А.

[Q.R] = qrinsert(Q,R,j,x) — изменяет Q и R таким образом, чтобы пересчитать разложение матрицы А для случая, когда в матрице А перед j-м столбцом вставлен столбец х. Входные значения Q и R представляют QR-разложение матрицы А как результат действия [Q,R]=qr(A). Аргумент х — вектор-столбец, который нужно вставить в матрицу А. Аргумент j определяет столбец, перед которым будет вставлен вектор х.

0 0.6112 0.6163 0.7369

Вычисление собственных значений и сингулярных чисел

Во многих областях математики и прикладных наук большое значение имеют средства для вычисления собственных значений (собственных чисел, характеристических чисел, решений векового уравнения) матриц, принадлежащих им векторов и сингулярных чисел. В новой версии MATLAB собственные вектора нормализуются, иначе, чем в предыдущих. Основной критерий: либо V’V=I, либо V’BV=I, где V — собственный вектор, I — единичная матрица. Поэтому результаты вычислений в новой версии, как правило, отличаются. Ниже дан список средств решения векового уравнения, реализованных в системе MATLAB.

Несимметрические матрицы могут быть плохо обусловлены при вычислении их собственных значений. Малые изменения элементов матрицы, такие как ошибки округления, могут вызвать большие изменения в собственных значениях. Масштабирование — это попытка перевести каждую плохую обусловленность собственных векторов матрицы в диагональное масштабирование. Однако масштабирование обычно не может преобразовать несимметрическую матрицу в симметрическую, а только пытается сделать (векторную) норму каждой строки равной норме соответствующего столбца. Масштабирование значительно повышает стабильность собственных значений.

[D.B] = balance(A) — возвращает диагональную матрицу D, элементы которой являются степенями основания 2, и масштабированную матрицу В, такую, что B=D\A*D, а норма каждого ряда масштабированной матрицы приближается к норме столбца с тем же номером;

В = balance(A) — возвращает масштабированную матрицу В. Пример использования функции balance:

» А=[1 1000 10000:0.0001 1 1000:0.000001 0.0001 1]

Величина, связывающая погрешность вычисления собственных значений с погрешностью исходных данных, называется числом обусловленности (собственных значений) матрицы и вычисляется следующим образом:

cond(V) = norm(V)*norm(inv(V)) где [V.D]=eig(A).[ B=D\A*D, а норма каждого ряда масштабированной матрицы приближается к норме столбца с тем же номером; ]

eig(A) — возвращает вектор собственных значений квадратной полной или симметрической разреженной матрицы А обычно после автоматического масштабирования, но для больших разреженных матриц (в терминологии MATLAB —

это просто полные матрицы со сравнительно большим [Но небольшим по сравнению с числом нулей разреженной матрицы. Эталонное число нулей разреженной матрицы данного размера можно вычислить, применив к полной матрице этого же размера функцию sparse. — Примеч. ред.] числом нулей), а также во всех случаях, где помимо собственных значений необходимо получать и собственные вектора разреженной матрицы, вместо нее рекомендовано использовать eigs(A);

[V.D] = eig(A.B) — вычисляет диагональную матрицу обобщенных собственных значений D и матрицу V, столбцы которой являются соответствующими собственными векторами (правыми собственными векторами), таким образом что А V = В V D;

[V.D] = eig(A) — вычисляет диагональную матрицу собственных значений О матрицы А и матрицу V, столбцы которой являются соответствующими собственными векторами (правыми собственными векторами), таким образом что А V = V D.

Нужно использовать [W,D]=e1g(A’); W=W, чтобы вычислить левые собственные вектора, которые соответствуют уравнению W*A=D*W.

[V.D] = eig(A,’nobalance’) — находит собственные векторы и собственные значения без предварительного масштабирования. Иногда это улучшает обусловленность входной матрицы, обеспечивая большую точность вычисления собственных векторов для необычно масштабированных матриц;

eig(A,B, ‘qz’) — не требует, чтобы матрицы были симметрическими и возвращает вектор, содержащий обобщенные собственные значения, используя QZ-алгоритм; при явном указании этого флага QZ-алгоритм используется вместо алгоритма Холецкого даже для симметрической матрицы и симметрической положительно определенной матрицы В, так как может давать более стабильные значения, чем предыдущий метод. Для несимметрических матриц в MATLAB 6 всегда используется QZ-алгоритм и параметр ‘chol’ или ‘qz’ игнорируется;

[V.D] = eig(A.B) — возвращает диагональную матрицу обобщенных собственных значений D и матрицу V, чьи столбцы являются соответствующими собственными векторами, так чтобы A*V=B*V*D. Пример:

svd(X) — возвращает вектор сингулярных чисел. Команда svd выполняет сингулярное разложение матрицы X;

Источник

Число обусловленности

Вложения

Задача.docx (40.0 Кб, 36 просмотров)

Число обусловленности
Собственно по методом вычисления дали задание. Написать метод Гаусса с выбором по всей матрице.

Число обусловленности матрицы
Дана матрица 6 на 6 нужно рассчитать число обусловленности этой матрицы

Strelok45, переведите в doc или в рисунок.

Думаю правильно сказать «могут дать большие погрешности».

Вложения

Задача.doc (62.5 Кб, 22 просмотров)

Я пожалуй отвечу за всех.

Соответственно Вам придется покопаться в литературе, в которой есть больше оценок относительных погрешностей. Список литературы попросите у препода.

По-моему, выделять какой-то элемент вектора ошибки в данном случае не имеет особого смысла, в общей теории речь идёт только о норме вектора.
Лучшее обсуждение погрешностей я встречал в книгах:
Малькольм, Форсайт, Моулер «Машинные методы математических вычислений», 1980;

переработанное издание:
Каханер, Моулер, Нэш «Численные методы и программное обеспечение», 1998

Вот несколько отрывков:

Найти число обусловленности при обращении матрицы методом гаусса
Мне надо вычеслить число обусловленности при обращении матрицы методом гаусса с выбором ведущего.

Источник

Обусловленность матриц

Не всегда малость невязки гарантирует малость погрешности найденного решения.

Гауссово исключение с выбором главного элемента гарантированно дает малые невязки. Малость здесь трактуется относительно, т.е. по отношению к элементам матрицы A, элементам матриц в промежуточных вычислениях и к компонентам вычисленного решения.

Но даже если невязка мала, вектор ошибки не обязательно мал:

Обусловленность – это внутреннее свойство матрицы A, не зависит от метода решения СЛАУ. Матрицы с большим числом обусловленности дают большие ошибки при решении систем. Логарифм числа обусловленности приближенно равен числу значащих цифр, теряемых в решении системы Ax=b.

Число cond(A) измеряет насколько близка к вырожденной матрица A и, что еще важнее, насколько чувствительно решение системы Ax=b к изменениям в A и b.

A – вырожденная, если для некоторых b решение системы Ax=b не существует, а для других b оно будет не единственным. Если матрица A – почти вырожденная, то можно ожидать, что малые изменения A и b вызовут очень большие изменения в x.

Умножение x на матрицу A приводит к вектору Ax, норма которого может сильно отличаться от x||. Это изменение нормы прямо связано с чувствительностью матрицы.

Þ ||Ax|| £ M∙||x||

Þ m∙||x|| £ ||Ax||

Отношение M/m и называют числом обусловленности матрицы A:

обозначение cond от английского слова conditioned – обусловленный.

Но – норма, согласованная с нормой x.

Обозначим образ оператора Ax за y: y=Ax. Тогда x=A –1 y. При x¹0, y¹0.

cond(A)= A||∙||A –1 ||. (6.11)

Покажем, что cond(A) измеряет чувствительность к погрешностям. Пусть правая часть уравнения Ax=b получила приращение («возмущение») Db, т.е. вместо истинного вектора b используется приближенный вектор b. Реакцией решения x на возмущение Db правой части будет вектор поправок Dx, т.е. x+Dx – решение уравнения

A(x+Dx)=b+Db.

Так как Ax=b, ADx=Db, откуда Dx= A –1 Db. Нормируем равенства и воспользуемся свойством нормы:

||b|| = ||Ax|| £ ||A||∙||x||,

||Dx|| = ||A –1 Db|| £ || A –1 ||∙||Db||,

где матричная норма согласована с векторной нормой. Перемножим два неравенства одинакового смысла:

||b||∙||Dx|| £ ||A||∙||x||∙|| A –1 ||∙||Db||,

Легко показать, что то же самое число cond(A) служит коэффициентом роста относительных погрешностей при неточном задании элементов матрицы A. А именно, если матрица A получила возмущение DA и x+Dx – решение возмущенной системы

(A+DA)(x+Dx)=b,

то справедливы неравенства

С более точным соотношением зависимости относительной погрешности решения d_x от относительных погрешностей d_A и d_b одновременно можно познакомиться в учебнике В.М.Вержбицкого «Основы численных методов», с. 30.

Основные свойства числа обусловленности:

1. Так как M ≥ m, cond(A) ≥ 1.

2. Умножение матрицы A на число не меняет числа обусловленности:

cond(с∙A) = cond(A).

3. Если D – диагональная матрица, то

Если мы рассмотрим матрицу

Число обусловленности играет фундаментальную роль в анализе ошибок округления, совершаемых в ходе гауссова исключения. Пусть A и b заданы точно, x * – приближенное решение, полученное методом Гаусса в арифметике с плавающей точкой. Тогда

Основной результат в исследовании ошибок округления в гауссовом исключении принадлежит Дж.Х.Уилкинсону. Он доказал, что вычисленное решение x * точно удовлетворяет системе

где DA – матрица, элементы которой имеют величину порядка ошибок округления в элементах матрица A. Тем самым все ошибки округления могут быть слиты воедино и рассматриваться как единственное возмущение, внесенное в матрицу A в момент записи в память компьютера, само же исключение осуществляется без ошибок. В этом смысле метод Гаусса – лучший алгоритм решения СЛАУ. Контроль качества вычислений может быть осуществлен по вектору невязок только для хорошо обусловленных систем

Источник