1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 74
Текст из файла (страница 74)
http://www.nsc.ru/interval/Library/InteBooks)[87] Яненко Н.Н. Метод дробных шагов решения многомерных задач математической физики. – Новосибирск: Наука, 1967.[88] Bauer F.L., Fike C.T. Norms and exclusion theorems // NumerischeMathematik. – 1960. – Vol. 2. – P. 137–141.[89] Eckart C., Young G. The approximation of one matrix by another of lower rank// Psychometrika.
– 1936. – Vol. 1. – P. 211–218.[90] Gregory R.T., Karney D.L. A collection of matrices for testing computationalalgorithms. – Hantington, New York: Robert E. Krieger Publishing Company, 1978.[91] Hotelling H. Analysis of a complex of statistical variables into principalcomponents // J. Educ. Psych.
– 1933 – Vol. 24. – Part I: pp. 417-441, Part II:pp. 498-520.[92] Kreinovich V., Lakeyev A.V, Noskov S.I. Approximate linear algebra isintractable // Linear Algebra and its Applications. – 1996. – Vol. 232. – P. 45–54.[93] Kreinovich V., Lakeyev A.V., Rohn J., Kahl P. Computational complexityand feasibility of data processing and interval computations. – Dordrecht: Kluwer,1997.[94] Moler C. Professor SVD // The MathWorks News & Notes. – October 2006. –P. 26–29.[95] Moore R.E., Kearfott R.B., Cloud M. Introduction to interval analysis. –Philadelphia: SIAM, 2009.[96] Schulz G.
Iterative Berechnung der reziproken Matrix // Z. Angew. Math. Mech.– 1933. – Bd. 13 (1). – S. 57–59.[97] Stoer J., Bulirsch R. Introduction to numerical analysis. – Berlin-HeidelbergNew York: Springer-Verlag, 1993.[98] Varga R.S. Matrix iterative analysis. – Berlin, Heidelberg, New York: SpringerVerlag, 2000, 2010.[99] von Neumann J., Goldstine H.H. Numerical inverting of matrices of high order// Bulletin of the American Mathematical Society. – 1947. – Vol.
53, No. 11. –P. 1021–1099.Литература к главе 3453[100] Wilf H.S. Finite sections of some classical inequalities. – Heidelberg: Springer,1970.[101] Todd J. The condition number of the finite segment of the Hilbert matrix //National Bureau of Standards, Applied Mathematics Series. – 1954. – Vol. 39. –P. 109–116.Глава 4Решение нелинейныхуравнений и их систем4.1ВведениеВ этой главе рассматривается задача решения системы уравненийF1 ( x1 , x2 , .
. . , xn ) = 0, F2 ( x1 , x2 , . . . , xn ) = 0,(4.1).........Fn ( x1 , x2 , . . . , xn ) = 0,над полем вещественных чисел R, или, кратко,F (x) = 0,(4.2)где x = ( x1 , x2 , . . . , xn ) ∈ Rn — вектор неизвестных переменных,Fi (x), i = 1, 2, . . . , n, — вещественнозначные функции,F (x) = ( F1 (x), F2 (x), . . . , Fn (x) )⊤ — вектор-столбец функций Fi .Для переменных x1 , x2 , . .
. , xn нужно найти набор значений x̃1 , x̃2 , . . . ,x̃n , называемый решением системы, который обращает в равенства всеуравнения системы (4.1)–(4.2). В некоторых случаях желательно найтивсе такие возможные наборы, т. е. все решения системы, а иногда достаточно какого-то одного. В случае, когда система уравнений (4.1)–(4.2)4544554.1. Введениене имеет решений, нередко требуется предоставить обоснование этогозаключения или даже его вывод, и им может быть протокол работыпрограммы для ЭВМ и т.
п.Наряду с задачами, рассмотренными в Главе 2, то есть интерполяцией и приближениями функций, вычислением интегралов, задачарешения уравнений и систем уравнений является одной из классических задач вычислительной математики.Всюду далее мы предполагаем, что функции Fi (x) по меньшей меренепрерывны, а количество уравнений в системе (4.1)–(4.2) совпадает сколичеством неизвестных переменных. Помимо записи систем уравнений в каноническом виде (4.1)–(4.2) часто встречаются и другие формыих представления, например,G(x) = H(x)(4.3)с какими-то функциями G, H. Чрезвычайно важным частным случаемэтой формы является рекуррентный вид системы уравнений (уравнения),x = G(x).(4.4)в котором неизвестная переменная выражена через саму себя.
В этомслучае решение системы уравнений (или уравнения) есть неподвижная точка отображения G, т. е. такой элемент области определенияG, который переводится этим отображением сам в себя. Кроме того,рекуррентный вид уравнения или системы хорош тем, что позволяетдовольно просто организовать итерационный процесс для нахождениярешения, что мы могли видеть в Главе 3.Как правило, системы уравнений различного вида могут быть приведены друг к другу равносильными преобразованиями. В частности,несложно установить связь решений уравнений и систем уравнений вида (4.1)–(4.2) с неподвижными точками отображений, т.
е. с решениямиуравнений в рекуррентом виде (4.4). Ясно, чтоF (x) = 0⇐⇒x = x − ΛF (x),где Λ — ненулевой скаляр в одномерном случае или же неособеннаяn×n-матрица в случае вектор-функции F . Поэтому решение уравненияF (x) = 0является неподвижной точкой отображенияG(x) = x − ΛF (x).4564. Решение нелинейных уравнений и их системЕсли неизвестная x не явлется конечномерным вектором, а отображения F и G имеют весьма общую природу, то математические свойства уравнений (4.2) и (4.4) могут существенно различаться, так чтопри этом формы записи (4.2) и (4.4), строго говоря, не вполне равносильны друг другу. По этой причине для их обозначения часто употребляют отдельные термины — уравнение первого рода и уравнениевторого рода соответственно.Обращаясь к решению нелинейных уравнений и их систем, мы обнаруживаем себя в гораздо более сложных условиях, нежели при решении систем линейных алгебраических уравнений (3.48)–(3.49). Стройная и весьма полная теория разрешимости систем линейных уравнений, базирующаяся на классических результатах линейной алгебры,обеспечивала в необходимых нам случаях уверенность в существовании решения систем линейных уравнений и его единственности.
Длянелинейных уравнений столь общей и простой теории не существует.Напротив, нелинейные уравнения и их системы имеют в качестве общего признака лишь отрицание линейности, т. е. то, что все они «нелинейны», и потому отличаются огромным разнообразием. Из общихнелинейных уравнений и систем уравнений принято выделять алгебраические уравнения и системы уравнений, в которых функции Fi (x)являются алгебраическими полиномами относительно неизвестных переменных x1 , x2 , . . . , xn .4.2Вычислительно-корректные задачи4.2аПредварительные сведения и определенияНапомним общеизвестный факт: на вычислительных машинах (какэлектронных, так и механических, как цифровых, так и аналоговых)мы можем выполнять, как правило, лишь приближённые вычислениянад полем вещественных чисел R.
Для цифровых вычислительных машин этот вывод следует из того, что они являются дискретными и конечными устройствами, так что и ввод вещественных чисел в такую вычислительную машину и выполнение с ними различных арифметических операций сопровождаются неизбежными ошибками, вызваннымиконечным характером представления чисел, конечностью исполнительных устройств и т. п. Для аналоговых вычислительных машин данныетакже не могут быть введены абсолютно точно, и процесс вычисленийтакже не абсолютно точен. Потенциально все отмеченные погрешности4.2. Вычислительно-корректные задачи457могут быть сделаны сколь угодно малыми, но в принципе избавитьсяот них не представляется возможным. Получается, что реально• мы решаем на вычислительной машине не исходную математическую задачу, а более или менее близкую к ней,• сам процесс решения на ЭВМ отличается от своего идеальногоматематического прообраза, т. е.
от результатов вычислений в Rили C по тем формулам, которые его задают.Возникновение и бурное развитие компьютерной алгебры с её «безошибочными» вычислениями едва ли опровергает высказанный вышетезис, так как исходные постановки задач для систем символьных преобразований требуют точную представимость входных данных, которые поэтому подразумеваются целыми или, на худой конец, рациональными с произвольной длиной числителя и знаменателя (см. [2]), а всепреобразования над ними не выводят за пределы поля рациональныхчисел.Как следствие, в условиях приближённого представления входныхчисловых данных и приближённого характера вычислений над полемвещественных чисел R мы в принципе можем решать лишь те постановки задач, ответы которых «не слишком резко» меняются при изменении входных данных, т.
е. устойчивы по отношению к возмущениямв этих начальных данных. Для этого, по крайней мере, должна иметьместо непрерывная зависимость решения от входных данных.Для формализации высказанных выше соображений нам необходимо точнее определить ряд понятий.Под массовой задачей [13] будем понимать некоторый общий вопрос,формулировка которого содержит несколько свободных переменных —параметров — могущих принимать значения в пределах предписанныхим множеств. В целом массовая задача Π определяется1) указанием её входных данных, т. е. общим спискомвсех параметров с областями их определения,2) формулировкой тех свойств, которым долженудовлетворять ответ, т. е.
решение задачи.Индивидуальная задача I получается из массовой задачи Π путём присваивания всем параметрам задачи Π каких-то конкретных значений.Наконец, разрешающим отображением задачи Π мы называм отображение, сопоставляющее каждому набору входных данных-параметров4584. Решение нелинейных уравнений и их системответ соответствующей индивидуальной задачи (см. §1.3). Станем говорить, что массовая математическая задача является вычислительнокорректной, если её разрешающее отображение P → A из множествавходных данных P во множество A ответов задачи непрерывно относительно некоторых топологий на P и A, определяемых содержательнымсмыслом задачи.Те задачи, ответы на которые неустойчивы по отношению к возмущениям входных данных, могут решаться на ЭВМ с конечной разрядной сеткой лишь опосредованно, после проведения мероприятий,необходимых для защиты от этой неустойчивости или её нейтрализации.Конечно, скорость изменения решения в зависимости от измененийвходных данных может быть столь большой, что эта зависимость, даже будучи непрерывной и сколь угодно гладкой, становится похожейна разрывную.
Это мы могли видеть в §3.16в для собственных значений некоторых матриц, которые являются «практически разрывными»функциями элементов матрицы. Но определением вычислительно корректной задачи выделяются те задачи, для которых хотя бы в принципевозможно добиться сколь угодно точного приближения к идеальномуматематическому ответу, например, увеличением количества значащихцифр при вычислениях и т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
