Re: Метод Крамера

From

Sergei Katkovsky ()

To

George Shuklin

Date

2000-03-04T01:19:27Z

Area

RU.ALGORITHMS

From: "Sergei Katkovsky" <energoav@dialup.ptt.ru>


Hello! "George Shuklin" <George.Shuklin@p46.f744.n5030.z2.fidonet.org> wrote
in message:

>  >>  YR> Кpамеpа. А Кpамеpа очень легко pеализовать, достаточно написать
>  >>  YR> унивеpсальную функцию возpащающую опpеделитель из массива N*N и
>  >>  YR> усе.
>  SK> Угу. С числом операций порядка N!
>  SK> Посчитай, пожалуйста, определитель матрицы 25*25 по определению.
>  SK> Посчитаешь - возвращайся в эху.
> А я то тут при чем?

Так и адресовано не тебе, а YR - ответ-то  этом месте на его текст.

> Под устойчивостью понимается именно численная устойчивость, т.е. малые
> изменения нормы решения при малых искажениях входных значений.
(стандартный
> метод проверки на устойчивость)

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

>  >> численные методы? И медленные к тому же.
>  SK> Метод Крамера, конечно, самый медленный, особенно если считать
>  SK> определитель по определению, а вот метод Гаусса для матриц общего
>  SK> вида наискорейший.
> А какие еще методы ты знаешь?

Гхм. Ну, много разных. Для заполненных матриц общего вида принципиально
новым (в отличие от вариаций на тему Гаусса) являются ортогональные
разложения вроде QR. Всякие улучшения Гаусса для специального вида. Для
симметричных - LDLT, если матрица еще и положительно определена - метод
Холецкого (D в таком случае совпадает с Е, и остается LLT). Что там еще?
Метод прогонки для ленточных матриц. Ну еще для всяких других типов матриц
(теплицевых там, или еще каких) специальные методы есть. Да, для Гаусса
любого типа есть еще такая штука, как итерационное уточнение.
Итерационных еще больше. Всех не перечислить, короче. Только ты не думай,
что я их все наизусть знаю :)

>  SK> LDR, LDR - это что за зверь? L - понятно, D - понятно, а R?
> L-нижняя треугольная (с единичной диагональю), D - диагональная, R -
верхняя
> тереугольная. Из той же оперы LU,QR разложения.

Ты погоди - верхняя треугольная в таких методах завсегда U была. И зачем
тогда D, если матрицы разные, и в чем отличие от LU? А QR вообще-то из
другой оперы - Q-ортогональная матрица, R - действительно, верхняя
треугольная.

>  SK> На плохо обусловленных матрицах фигня выйдет всегда - самый хороший
>  SK> алгоритм не сделает задачу лучше, чем она есть, хоть бы вы считали
>  SK> даже с бесконечной точностью.
> А как насчет итерационных методов? Скажем, Зейделя, с оптимальным
параметром?

Да не в методе дело! Если сама задача плохо обусловлена, никакой метод ее не
сделает лучше. Он может сделать только хуже.

>  SK> P.S. Удивительно - раза в два месяца кто-нибудь так или иначе да
>  SK> предлагает считать определитель по определению.
> Это зависит от матрицы. Разреженные матрицы для увеличения точности можно
> счиать и по определению.

Меня всегда удивляет, почему думают, будто вычисление определителя по
определению повышает точность? Там на каждом действии используется
вычитание, и гарантии от полной потери точности никто не даст.

Сергей Катковский


--- ifmail v.2.15dev4
 * Origin: Fidolook Express page: http://fidolook.da.ru (2:5020/400)