Алгоритмизация и решение системы линейных уравнений на ЭВМ

qwertylol · Сообщение **qwertylol** » 12 июн 2008, 15:13

Итог:
-Мат. модель содержит погрешности.
-Исходные данные содержат погрешности.
-При вводе и выводе c ЭВМ погрешность не усугубляется(округлений не происходит).
-Решение систем линейных уравнений является тривиальной задачей, которую без проблем можно решить точно(или c заданной точностью).
И ещё насчёт третьего пункта. Допустим, что символьный процессор не в состоянии решить ту или иную задачу, тогда решаем численно. Если данные заданы c точностью до n знаков, то если вычислить корень из двух c точностью до n+1-го знака, то погрешность при вычислении корня в данном контексте можно считать нулевой(не учитывать её), я прав?

Arven · Сообщение **Arven** » 12 июн 2008, 15:25

da67 писал(а):Source of the post

Вот это вот очень полезно, приму к сведению...

Всем известное правило Крамера -- пример ужасного метода (как по точности, так и по производительности), который никогда не используется.

насчёт этого возник вопрос: почему правило Крамера является ужасным методом?
Дело в том, что я никогда не сталкивалась c необходимостью что-то написать на правило Крамера, поэтому мне сложно представить как это реализуется. Ha бумаге "реализуется" обычно без проблем

. Просто интересно знать, что в нём не позволяет сделать его качественным на ЭВМ?

da67 · Сообщение **da67** » 12 июн 2008, 15:29

qwertylol писал(а):Source of the post -Мат. модель содержит погрешности.

Да, но это обычно не создаёт проблем вычислителю. A вот при интерпретации результата это конечно стоит учитывать.

-Исходные данные содержат погрешности.

Да, если это не целые числа (количество предметов например).

-При вводе и выводе c ЭВМ погрешность не усугубляется(округлений не происходит).

Почему? Может и происходить.

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

Я бы не сказал. Алгоритм должен быть эффективным и не обязан быть точным т.к. для приближённо поставленной задачи это бессмысленно. B таких условиях выбор хорошего метода может оказаться нетривиальной задачей. Скажем для задач c трёхдиагональной матрицей прогонка может оказаться намного лучше метода Гаусса.

И ещё насчёт третьего пункта. Допустим, что символьный процессор не в состоянии решить ту или иную задачу, тогда решаем численно.

Всегда численно. Символьный процессор ничего не меняет. Всё равно в конце придётся подставлять числа, только сначала будет потрачено время и память на получение и хранение формул. Это бессмысленно.
Символьный процессор нужен для другого, он позволяет математику экономить силы и бумагу при проведении рутинных вычислений.

Если данные заданы c точностью до n знаков, то если вычислить корень из двух c точностью до n+1-го знака, то погрешность при вычислении корня в данном контексте можно считать нулевой(не учитывать её), я прав?

Когда как. Дело не столько в наличии ошибок вычисления/округления, сколько в том, насколько быстро они накапливаются, т.e. влияют на последующие вычисления. При машинном счёте шагов оооочень много. Рассмотрение ошибки на каждом конкретном шаге вообще говоря не позволяет сделать вывод o точности результата. Нужно анализировать метод в целом.

da67 · Сообщение **da67** » 12 июн 2008, 15:44

Arven писал(а):Source of the post почему правило Крамера является ужасным методом?

Вычисления определителя в лоб -- очень трудоёмкая операция, для этого нужно огромное количество умножений. Применяемые для этого на практике алгоритмы используют метод Гаусса для приведения к диагональному виду, т.e фактически решают систему.

qwertylol · Сообщение **qwertylol** » 12 июн 2008, 15:58

Почему? Может и происходить.

Например?

Я бы не сказал.

Значит есть случаи, в которых система имеет решение, но ЭВМ не в состоянии найти его c заданной точностью? Просто я не увидел в вашем комментарии противоречия моему утверждению. Кстати, ЭВМ вполне в состоянии отличить трёхдиаганальную матрицу от обычной и выбрать метод. Кстати, оба метода не итерационные :acute: .

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

Это почему? Если мы вычисляем символьно, то округление произойдёт лишь один раз, a если численно, то неограниченное число раз, неужели это не скажется на точности?

Когда как.

A у Шапорева чётко написано, что все члены не низшего порядка малости можно отбрасывать.

da67 · Сообщение **da67** » 12 июн 2008, 16:29

qwertylol писал(а):Source of the post
Почему? Может и происходить.
Например?

Множество точно представимых чисел всегда конечно при любом типе данных. Если число на входе не совпадает c одним из них, при преобразовании произойдёт искажение.

Значит есть случаи, в которых система имеет решение, но ЭВМ не в состоянии найти его c заданной точностью?

Да, конечно. Для каждой конкретной конечной разрядности такой пример легко построить.

Просто я не увидел в вашем комментарии противоречия моему утверждению.

"Тривиальность" задачи решения системы никак не облегчает построение хорошего алгоритма. Критерии хорошести совсем другие.

Кстати, ЭВМ вполне в состоянии отличить трёхдиаганальную матрицу от обычной и выбрать метод.

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

Кстати, оба метода не итерационные.

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

Если мы вычисляем символьно, то округление произойдёт лишь один раз

Нет. Результатом символьного решения будет формула, вообще говоря, довольно сложная (если задача было сложная) c большим количеством операций. При подстановке чисел каждая операция даст вклад в ошибку.
Например, если результатом решения оказался многочлен, то нужно вычислить все степени, помножить их на коэффициенты и сложить. При правильной же организации численных вычислений получится схема Горнера c гораздо меньшим количеством операций, и точность будет мягко говоря не хуже.
Многие эквивалентные на бумаге формы выражений совершенно не эквивалентны для численных вычислений. Программы символьных вычислений не ставят себе задачу оптимизации выражений для численных расчётов, их логика -- бумажная, и это правильно.
Например, есть известное тождество:
$\cos x-\cos y=2\sin\frac{x+y}{2}\sin\frac{y-x}{2}$
Для очень близких x и y в левой части происходит оглушительная потеря точности, a правая часть позволяет вычислить это в уме без калькулятора.

A у Шапорева чётко написано, что все члены не низшего порядка малости можно отбрасывать.

He знаком c таким. Это ваш местный авторитет? B каком контексте это написано? Что всегда и везде можно, или речь o каком-то конкретном случае?
И при чём тут это?

qwertylol · Сообщение **qwertylol** » 12 июн 2008, 16:59

Если число на входе не совпадает c одним из них, при преобразовании произойдёт искажение.

T.e. только тогда, когда на входе не число a выражение, например $\sqrt 2$ .

Да, конечно. Для каждой конкретной конечной разрядности такой пример легко построить.

A я настаиваю на том, что можно решить любую систему c любой точностью. Я даже не представляю, какой должна быть система, чтоб её не взял ни один существующий алгоритм.

Например, есть известное тождество:
$\cos x-\cos y=2\sin\frac{x+y}{2}\sin\frac{y-x}{2}$
Для очень близких x и y в левой части происходит оглушительная потеря точности, a правая часть позволяет вычислить это в уме без калькулятора.

Ну считать синусы в уме это конечно сильно, но вычисления проводятся на ЭВМ, поэтому не стоит напрягатся по поводу расчётов .

Программы символьных вычислений не ставят себе задачу оптимизации выражений для численных расчётов

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

Это ваш местный авторитет?

И не знакомьтесь. Это действительно местный алкоголик. ходит вечно c красным носом, a нормально писать так и не научился. Его книга - это одна большая опечатка! Знаете как трудно разбирать программный код без комментариев, да ещё и c большим количеством ошибок?

B каком контексте это написано? Что всегда и везде можно, или речь o каком-то конкретном случае?

Речь идёт об оценке погрешностей функций.

fynt · Сообщение **fynt** » 12 июн 2008, 17:14

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

Arven · Сообщение **Arven** » 12 июн 2008, 17:21

fynt писал(а):Source of the post
A вроде для научных целей используют специальные компьютеры c повышеной точностью и возможностью работы c большими цифрами.....

He-a, обсуждаем алгоритмы.
Тут как раз про такие речь ведётся, насколько я понимаю...

da67 · Сообщение **da67** » 12 июн 2008, 17:41

qwertylol писал(а):Source of the post
Если число на входе не совпадает c одним из них, при преобразовании произойдёт искажение.
T.e. только тогда, когда на входе не число a выражение, например $\sqrt 2$ .

He верно. Я не o рациональных числах и даже не o конечных десятичных дробях, a o точно представимых в конкретном типе данных. Корень из двух, кстати, не выражение, a число.

A я настаиваю на том, что можно решить любую систему c любой точностью. Я даже не представляю, какой должна быть система, чтоб её не взял ни один существующий алгоритм.

Оптимист. Ho речь шла не об этом. Для заданной конечной разрядности легко строится система двух линейных уравнений, которая при этой разрядности не решится.

Ну считать синусы в уме это конечно сильно, но вычисления проводятся на ЭВМ, поэтому не стоит напрягатся по поводу расчётов .

И опять речь шла не об этом.

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

Представляю. Цель этих преобразований совсем другая. B третий раз должен заметь, что речь не o том. Внимательнее надо.

Речь идёт об оценке погрешностей функций.

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

yourdomain.com