Как решать СЛАУ

[xagiwo]

Что можно почитать про практическое решение СЛАУ? Желательно что-нибудь попроще. Слышал, что на практике используют метод сопряжённых градиентов, но мои попытки понять его (открыл статью в Википедии) провалились.

[Pphantom]

xagiwo в сообщении #1558933 писал(а):

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

Это не самый простой вариант (и далеко не всегда нужный). Лучше бы начать с уточнения, какие системы решать требуется: характерные размеры, специфические свойства матрицы (если они есть), требуемое быстродействие, выбор CPU/GPU и т.д.

[xagiwo]

Pphantom в сообщении #1558937 писал(а):

Лучше бы начать с уточнения

Ну, на самом деле, моя цель — устранить комплексы по поводу того, что курс алгебры я закончил, а СЛАУ решать так и не научился Так что применяться всё это будет, вероятно, к системам $10 \times 10$ — $100 \times 100$ (видимо, определённым), заполненными случайными циферками.

Хотелось бы рассчитывать на что-то как можно более широкого охвата, чтобы максимизировать вероятность, что мне это реально понадобится.

[Pphantom]

xagiwo в сообщении #1558938 писал(а):

Хотелось бы рассчитывать на что-то как можно более широкого охвата, чтобы максимизировать вероятность, что мне это реально понадобится.

Так ведь такого не бывает. Одно дело - решать системы с разреженными матрицами размера порядка $10^6$, другое - то, что вы описали, третье - что-нибудь еще.

Конкретно в данном случае - самый стандартный метод Гаусса (возможно, с выбором ведущего элемента). Все остальное либо не всегда будет работать, либо не стоит затрат времени на реализацию.

[zykov]

Зависит от матрицы.
Если разреженная (много нулей), то это одно.
Если не разреженная (или просто маленькая, вроде 10x10 или 100x100), то это всё давно хорошо известно - матод Гаусса, LU-факторизация (делают с pivoting для численной стабилизации).

[vpb]

Форсайт и Молер, Численное решение систем линейных алгебраических уравнений
Trefethen, Bau, Numerical linear algebra
и к ним компаньоном
Overton, Numerical computing with IEEE floating point arithmetic
Имхо, три самых полезных книжки по предмету (но это имхо).

-- 01.07.2022, 01:27 --

xagiwo в сообщении #1558938 писал(а):

а СЛАУ решать так и не научился

экий вы кокетливый.

-- 01.07.2022, 01:31 --

Еще несколько источников:
в книге "Лекции лауреатов премии Тьюринга за первые 20 лет" --- лекция Уилкинсона.
Бахвалов, Численные методы, несколько параграфов в соответствующей главе
Наконец, основательная книжка
Higham, Accuracy and stability of numerical algorithms
(соответствующие главы из нее). В общем, читать --- не перечитать...

[Евгений Машеров]

xagiwo в сообщении #1558933 писал(а):

Что можно почитать про практическое решение СЛАУ? Желательно что-нибудь попроще. Слышал, что на практике используют метод сопряжённых градиентов, но мои попытки понять его (открыл статью в Википедии) провалились.

Если "для себя поупражняться" - Гаусс, с частичным выбором ведущего элемента. Он же и для всех матриц умеренного размера и заполненных. Если нужна суперточность - какие-то вращения. Сопряжённые градиенты хороши тем, что всю матрицу хранить не надо. Надо лишь иметь возможность получать значения её элементов. Чтобы получить произведение этой матрицы на некоторый вектор (скажем, если матрица сильно разреженная, или элементы её могут вычисляться "по надобности", а не храниться). При этом сходится быстрее, чем простые итерации. Востребовано, скажем, в методе конечных элементов.

[xagiwo]

Спасибо всем.

Евгений Машеров в сообщении #1559038 писал(а):

Сопряжённые градиенты хороши тем, что всю матрицу хранить не надо.

Слышал, что ещё тем, что в Гауссе быстро копится ошибка из-за деления на каждом шагу. Это не так?

[B@R5uk]

При вычислениях с плавающей запятой ошибка копится всегда. А вот как быстро это происходит зависит от того, что и как считается. Вон, даже разность

$$R\left(a,\,b\right)=a^2-b^2=\left(a+b\right)\left(a-b\right)$$

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

-- 02.07.2022, 10:12 --

Алсо, если вам реально надо использовать СЛАУ для вычислений, то я бы на вашем месте установил MATLAB и не парился. Постепенно отточите навыки именно использования, а потом будет уже куда яснее, нужно вам писать что-то своё для дела или нет.

[zykov]

xagiwo в сообщении #1559081 писал(а):

Слышал, что ещё тем, что в Гауссе быстро копится ошибка из-за деления на каждом шагу.

Если делать Гаусса в лоб и делить большое на маленькое, то даже не копится, а преумножается.
Для этого и делают pivoting, чтобы всегда делить меньшее на большее (pivot выбирают, чтобы был больше всех других).
В этом случае ошибка наоброт подавляется, т.к. множитель меньше 1. (Я ссылку выше давал на LU.)
А раз подавляется, то даже и не копится. Метод безупречен, не считая вычислительного времени, которое впрочем всё равно разумно.

[vpb]

xagiwo в сообщении #1559081 писал(а):

Слышал, что ещё тем, что в Гауссе быстро копится ошибка из-за деления на каждом шагу. Это не так?

Жаль, что вы упомянутую выше лекцию Уилкинсона на успели прочитать...

[vpb]

zykov в сообщении #1559091 писал(а):

В этом случае ошибка наоброт подавляется, т.к. множитель меньше 1. (Я ссылку выше давал на LU.)
А раз подавляется, то даже и не копится.

Это рассуждение совершенно некорректное, мутное. Строгое рассуждение по поводу численной устойчивости метода Гаусса совсем другое.

[svv]

http://dxdy.ru/post1537111.html#p1537111

[xagiwo]

vpb в сообщении #1559099 писал(а):

Жаль, что вы упомянутую выше лекцию Уилкинсона на успели прочитать...

И в планах не было. Если Вы даёте мне 6 книг — я открываю одну, а на остальные смотрю как на запасной план, если что-то будет непонятно (а английские источники тем более меня пугают).

Но теперь я прочитал. Мало что понял — вероятно, потому что это статья о развитии вычислительной математики, написанная 50 лет назад, а я ужасно невежественный (я и о том, что сейчас происходит, не в курсе). По моему вопросу — видимо, однажды Уилкинсон удивился как раз тому, что метод Гаусса мало ошибается, а далеко после выяснилось, почему?

[vpb]

xagiwo в сообщении #1559114 писал(а):

По моему вопросу — видимо, однажды Уилкинсон удивился как раз тому, что метод Гаусса мало ошибается, а далеко после выяснилось, почему?

Верно. Хотя не так уж далеко после это выяснилось, лет через десять.