Линейная алгебра: Гаусс, Гаусс — Жордан, LU, QR, умножение матриц — авторское изложение

ru · official · sha256:e4017f24c684e9d0ce4e6677d4dd385ee885f641ee6bb4d5de28e106bc070138

§1. Элементарные преобразования, ведущий элемент и устойчивость Матрица размера m на n есть таблица чисел с двумя индексами. Элементарные преобразования строк — перестановка двух строк, умножение строки на ненулевое число и прибавление к строке другой строки, умноженной на число. Каждое из них обратимо и не меняет множества решений системы линейных уравнений; на этом стоят §2 и §3. Ступенчатая форма: в каждой ненулевой строке первый ненулевой элемент — ведущий — стоит правее ведущего элемента предыдущей строки, а нулевые строки стоят внизу. Приведённая ступенчатая форма дополнительно требует, чтобы ведущие элементы равнялись единице и были единственными ненулевыми в своих столбцах. Ведущий элемент шага — элемент, на который делят при исключении. Выбор ведущего элемента — не деталь: при точной арифметике над рациональными числами он влияет только на размер промежуточных чисел, а при вычислениях с округлением определяет устойчивость. Частичный выбор берёт наибольший по модулю элемент столбца; полный выбор берёт наибольший по модулю в оставшейся подматрице и требует перестановки столбцов, то есть перенумерации неизвестных. Настоящее изложение всюду различает ТОЧНУЮ арифметику и арифметику с округлением и говорит, к какой относится утверждение. Смешение их — источник ложных утверждений об устойчивости. Ортогональная матрица — квадратная матрица, произведение которой на свою транспонированную даёт единичную. Умножение на ортогональную матрицу сохраняет евклидову длину вектора; отсюда и происходит устойчивость методов, основанных на отражениях и вращениях. Отражение Хаусхолдера — ортогональное преобразование вида I − 2·v·vᵀ/(vᵀ·v), отражающее пространство относительно гиперплоскости, перпендикулярной вектору v. Оно позволяет одним преобразованием обнулить весь поддиагональный кусок столбца — в отличие от вращений Гивенса, обнуляющих по одному элементу.

Ссылаются нормы: AnswersHere, f-05366b89a52c200367cfc324, f-1cd00db9a7a04f3d54969e80, f-23a9f22b496d295cc91faa51, f-27314198b1e1ed048eb77ed9, f-2af7493dccd81917f802ecd0, f-2f76b652cbfd0ad099ec7f04, f-331d103ec360ee5d7ea6edad, f-3652c247689eb5e207490571, f-57aa14b7df9bb45aa6e575d5, f-5d7a1307c97c6cc4cd3bf50e, f-5dcb2b3f649b94f98d3cccd5, f-5f2309c76e3e128178e8e182, f-60a20e0d869c4a940ef0ced6, f-66c9830b6b765967cdeec677, f-69f86138460b704821842bd8, f-72c6603b27d22de282d80b33, f-735a573f312a7da8d0fcf55c, f-7788a58683fecce11775b6bd, f-79c4b850ba1dfd267ba3116b, f-7c240e6ea493acd35f2bce45, f-7eae70824826abe8e9b4bbf8, f-812026f6e30d0caa5b0845db, f-829a4d0b90ef5efdc40c8ada, f-83c771a17a58c254598c9169, f-8dff26751f8d443d4a6ff8e0, f-9977f25d57752b55a7754ec3, f-9bdcffad6c67cd8ffa84b428, f-9ed7a69ccf04f512ffc9da94, f-ac36a9cb8b625046c2776ec6, f-b90625d47e2ad79984755a33, f-cd75bc67f4c0379cfbaece4a, f-cf1bf576e70b8e74e43e792b, f-d21964dfda402cad86cd41b3, f-e52c557942b060aea732e336, f-e746b1f79021a4a8b3433a66, f-f0d76f51a621b007e33890ee, f-f1b8717c07db13279f85d324, f-f3a5fe571f830776a730bed0, f-f8026331dcb8277af38659ab, f-fb690cc6b7a451480736c778

ru · official · sha256:a5810d6156eb714190cb0c39bd2d6c232bc9b770bd02880369a608ebc2f8914e

§2. Исключение Гаусса Задача: по матрице получить ступенчатую форму и ранг элементарными преобразованиями строк. Вариант — прямой ход с частичным выбором ведущего элемента. Обрабатываются столбцы слева направо. Для текущего столбца среди строк ниже текущей ведущей ищется строка с наибольшим по модулю элементом; если все они нулевые, столбец пропускается без увеличения номера ведущей строки. Иначе найденная строка меняется местами с текущей ведущей, и из всех строк ниже вычитается ведущая, умноженная на подходящий множитель, так что элементы столбца ниже ведущего обнуляются. Пропуск столбца БЕЗ увеличения номера ведущей строки существен: без него ступенчатая форма прямоугольной матрицы строится неверно. Это самая частая ошибка изложений, написанных только для квадратных невырожденных матриц. Инвариант: перед обработкой столбца j первые k строк образуют ступенчатую форму по первым j столбцам, а элементы ниже ведущих обнулены. Ранг равен числу ведущих элементов по завершении. Определитель квадратной матрицы равен произведению диагональных элементов ступенчатой формы, умноженному на знак перестановки строк; масштабирование строк на этом ходе не применяется, поэтому определитель не искажён. Оценка: порядка двух третей куба размера умножений при квадратной матрице. Точная арифметика над рациональными числами даёт верный результат всегда; при вычислениях с округлением частичный выбор ведущего элемента ограничивает рост погрешности, и это утверждение принадлежит источнику. Исполнимая реализация этого хода в репозитории — `calc.row_reduction`; она ведёт журнал элементарных преобразований и строит матрицу перехода.

Ссылаются нормы: f-0140d2ee07f53a714438c1fa, f-04ba9f136fdbf03b50062ae7, f-050a72fdbac4afc3a0cc2e1e, f-14d8f39234d5bc05741db74c, f-21b3d8260def1600b09b729e, f-22d5cc16d2009a992f7b5402, f-23e31ce0a305f7d1c6f5b87e, f-253cdd89fd5015716d3d9db2, f-25f4412147ed4aeacb5d9bff, f-2b13c2eec7909c108c7dd208, f-2be38594711b55ddbda48841, f-323c1ae5334ffe7a29a8dac5, f-32812b8feee00fd1499ea3f4, f-32de3c8d5412267037ace638, f-33bb6d5b838ea69dc532edf6, f-37e7b47515f2e4529fd77a42, f-39de3a0e2bd066f81d7bcf45, f-3eedebe2d8569c8f5cd285d6, f-3fcfe3382739fe6c3dec6bc0, f-3fe9e0b77bcf519ae319e022, f-40ea7eeeac677fdaf4799acb, f-435b0546359a9cc44ac8d914, f-47d6958aa30631f181e0f55a, f-48e191856fad2456873d80fc, f-4f05ac3196c6a74d388b7b48, f-51e198a1ea10c4a716891ea0, f-54aaeb2a2d72e0384d4e1c58, f-5a666f4d68435093b999a1eb, f-5c5273e8251cd5fc73a956f3, f-5f6162271c8844ed40a78079, f-65be81fab19ea325fa78de42, f-66600c06157ebd089e70aae5, f-67f009173ddb294ba7876083, f-6a7d47c908e83e912d3e0148, f-6c53cfe64ca27338ebbaca51, f-72d343974e6b2885cc35333f, f-766bd4e228d29141e5c58a0b, f-7967ac235cafd17ec900c718, f-7bfcba3ab6cb456337c5781d, f-7cd8880d4a41a7b90430040d, f-7d350ec6abd7a3d9e0111a4e, f-7d65994649a7bdfd76653260, f-7e2d24cfe618390b0e1f0926, f-81621b35b91025dad56f545f, f-8271d226f38ee9860e15e9d3, f-83dce1a42779146616f250e0, f-842ea977a60377a4463a301e, f-859b6f1991dd6c302b220953, f-86b5d6974f9c73f1e00cb5c8, f-891d3a874d502d6969732142, f-8a18e8181770b34f5ea70440, f-8a5d315acff8d0b3dc0c783a, f-8b47a61d04e38c8a07c97a0b, f-920ed8ff29d7124208595a5f, f-94efb10ea68b4ca2658919da, f-950b992a6dd80c26a11b8163, f-95da73316c6daa29b61d99d4, f-979c5d85c63230442ecf24cf, f-97b9b22b9f57bca9919d06f4, f-9cf45c1f7106323f1e10bb2a, f-9f53ab01e86edf2852c36ab3, f-a1eed7f24bdab93d00de6eaa, f-abcc6a122cdd913bed939631, f-ac7ff053ba09fb29a5dc1673, f-b14b3d3274f3fcf182884633, f-b89acdf5d10ba71e025bbaad, f-b9a2098152248e8707899866, f-bf8c0fcabec5a4236987c1a5, f-c0a8ec709c873cd99d476eea, f-c0d9f6436d96c6f4fd137af2, f-c0e3bc07aa3a1f444d4edab5, f-c396ee27f47bfc6fc5899db6, f-ce6df0d95b0709c61ee34b78, f-d11c552114d50edc3baef31b, f-d1f2cbb440b257bfd0a3ebdd, f-d20ea8d66fdf1b2aeec6016a, f-d371ce5d687fa7c08945294e, f-d79b009bf2f891618f5c6ddd, f-d7e985c9313b9fda822d17ad, f-d8b63484e859c159d3a2e951, f-d98722c3dc2242e30021d005, f-e0c0a15ca7334257e7657b0b, f-e48ddcbb0b9bc4320fc052e7, f-e565ccd29f26ec5aad287cbd, f-e57e83c34961c58658796a6b, f-ea3dd0f912c2a93637f844b0, f-ede09582fc4d5e932a41272b, f-f0ae718c308bb917cd14b04c, f-f0e6ccc6abe86789928dcc0c, f-f0ec9534faac7b5d6211fc87, f-f0eeff4f7cb68e341627bd97, f-f998018acdff5beed9d844a1, f-fb6c6383fc39c2b534cac9fd, f-fca9588324a524aa736415f4, f-fcbde8ff50671169d3f163d2, f-fd18ed25853b9de862cf1b01, f-fd6cc5c484c8e8a16d6139fe

ru · official · sha256:6885843542b88466ab9e0840eb6a2de75b1b7cc840da901067afb69ad5de3dd9

§3. Метод Гаусса — Жордана Задача: получить ПРИВЕДЁННУЮ ступенчатую форму. Вариант — прямой ход §2 и обратный ход с нормировкой ведущих строк и обнулением столбцов вверх. После прямого хода ведущие строки просматриваются снизу вверх. Ведущая строка делится на свой ведущий элемент, после чего из всех строк ВЫШЕ вычитается ведущая, умноженная на их элемент в ведущем столбце. Отличие от §2 — именно обратный ход. Он и делает форму приведённой: ведущие элементы становятся единицами и единственными ненулевыми в своих столбцах. Приведённая ступенчатая форма ЕДИНСТВЕННА для данной матрицы, тогда как ступенчатая форма — нет. Это утверждение источника, и оно объясняет, почему результат §3 не зависит от выбора ведущих элементов, а результат §2 зависит. Обращение матрицы получается применением того же обратного хода к расширенной матрице из исходной и единичной; если левая часть не приводится к единичной, матрица вырождена, и обратной не существует. Оценка: порядка куба размера умножений — примерно в полтора раза больше, чем у §2. Для решения ОДНОЙ системы обратный ход подстановкой дешевле; §3 выгоден, когда нужна сама приведённая форма либо обращение.

Ссылаются нормы: f-03423117bd2d70f27fa57041, f-052ae1f25f3c5f96b9466499, f-069439c97f15df6dfe390d8b, f-0a49356868501232a98db4fe, f-0b6a4cca080b5f3d48673a6f, f-0c055e34bed22312c8064ddb, f-11cfc40fc7c61be1cd981e14, f-154d9039ddec951fb2edbb40, f-1b067f676b9ccefb6b571706, f-1be94fa93f16f407707f1cc5, f-1c79f3ece61f88d855164b18, f-1cbe66584e10c977cc1b6a5d, f-1e27c35be188131863c5c754, f-1e9f2950698cd384ac076ef4, f-2b00db4d305943f56be99b33, f-2cc94c802bb8ab77efd17844, f-347a0cfd4b708f825e7ce39d, f-386f9e313be6a787bcbd7ae1, f-38831cdd6708de2d26b3d376, f-391cfc059565daa313fe1b94, f-3dd96563380e5528a1982bd1, f-403ba2712b5e229a028ef39e, f-4257741898f9df77cf55f9cb, f-43a22e0b989a340cf979c201, f-4f853ac473420d9d70f0e235, f-50a5f7bafb4fdc4cfcd158de, f-534b12bde7806b1ff0531e59, f-538785a58fcacc989773531c, f-64424f8d366d4e6fe539f41a, f-657eaaacf85130f8ed956ba0, f-65827dc2f362c2a3c724b586, f-6b1f15da363768778540b199, f-6ca19858434935905ee2b205, f-71e6dd5b46b07d352811722c, f-71ea8229d06b0ca6497438ed, f-7815bfa7bf9f7c3ce6bbe85f, f-7a4d3cbf925723e69bda8155, f-7addb4479d9d48f6412c1ce1, f-82e7f0606adc3532bcd3e9a8, f-853140d0c44d63cbacfcf000, f-9384b196d3078bb48b55d32b, f-93b64898134c3b466cdb1e9d, f-93b7140c7b0ece00889db875, f-a14d845606afb1af2ae7a293, f-a1adc5ef480cf0b55ba46770, f-a4b62f0b41990bac2efffc6c, f-a7891056855594d1c7982537, f-a9e117728077476fbef86f84, f-a9efa3689e1e047fe64509cc, f-aa53d2e4922b0d0f8cf2b3fa, f-aa69efe16f773efb3e1ee4a7, f-aeafea98cdcaeb2c687f6444, f-b103119f039592b84b3998ac, f-b8798280a2e7119e831e5699, f-be0e0f05962f71ad1c0234ed, f-bf8559a19f73df6bee1e1657, f-cb11627008aefa12c017f0e1, f-cdaa350bce1a5bf15f68f519, f-cf89b2f238d72aeee53442de, f-d5834c526cb8789783a79adf, f-d9a6f3faa90097b879fccfd4, f-db5f0d9af2025699e8ce69ec, f-de0619d089963ac2d322b69e, f-de4040854df75c05d0dd8959, f-df31ba1c21599c9ea2df2b46, f-e2ff686b6d91524b7ed04c9b, f-e3343ba4f7125f996710028a, f-e3f9737ba9d3244aaa6969bf, f-e5614e004f26ab34b597af57, f-e7d2d344d5bb2854e49ae503, f-e8e1d09082c6b4a8201af950, f-eaa1c13d703692589203f0c0, f-eb50c1ecbd560f7632611b8a, f-ec49abe59ecf5d9e64252dda, f-f38eba8d7b15f21971b818fa, f-f39f9752fa6e5c302dc5949c, f-f3cc355037aac1b21bf2937b, f-f505ae7d44968687e9bdc0fe, f-f7dc2853ffd7126af7864c9e, f-fca929fb8e0971529118f0ca

ru · official · sha256:b7c166a7ea9af04192e05db46bac9bd3f014d9c57267a4b38c6e2cbc3d5f8a41

§4. LU-разложение с выбором ведущего элемента Задача: по квадратной матрице A найти перестановку строк P, нижнетреугольную L с единичной диагональю и верхнетреугольную U, для которых P·A = L·U. Вариант — с частичным выбором ведущего элемента. Ход тот же, что у §2, но множители исключения не выбрасываются, а СОХРАНЯЮТСЯ на месте обнулённых элементов: они и образуют L. Перестановки строк записываются в P и применяются также к уже накопленной части L. Сохранение множителей на месте нулей — существо метода: L и U хранятся в одной матрице без дополнительной памяти. Это и отличает LU от простого исключения, у которого множители теряются. Без выбора ведущего элемента разложение существует не для всякой невырожденной матрицы: матрица с нулём в левом верхнем углу не раскладывается. С частичным выбором разложение P·A = L·U существует для ЛЮБОЙ невырожденной матрицы — утверждение источника, и опускать условие «с перестановкой» нельзя. Смысл разложения: решив однажды, систему с той же матрицей и разными правыми частями решают двумя треугольными подстановками порядка квадрата размера вместо куба. Именно ради этого LU и хранят. Инвариант: после обработки k столбцов первые k столбцов L и первые k строк U вычислены, и P·A совпадает с L·U на этой части. Оценка: та же, что у §2, — порядка двух третей куба размера умножений; дополнительной памяти нет.

Ссылаются нормы: f-00fd81c9dde86309414886eb, f-02022c381254154143401a56, f-022e01de6bbb6ae1f46eaf52, f-05cc031ba46e78b6753ead78, f-0d54bbacb0a838f2cb6dde6b, f-0e166af4627c994e6bc5a20d, f-0f64034b83ff7a8f02295480, f-1023f723c0a77093aca5b7ce, f-113338c7edec36caa4b2319a, f-1beedd7b6594f2389a48d7de, f-20e3f1f724e19b0734fa3f82, f-229593737ee24234e72555ed, f-274cd82e3f6556b56fcaaa60, f-29f675f2c975833749f17ec0, f-2a29460fc1156c67c731ee41, f-2df834436dd359d5cdb934a1, f-2e792bd1ede954afd210831e, f-2f8352c89e02deae0c23e041, f-30569efa9adb00fdff2530c4, f-35d941ab4ff3079372409e61, f-3997e43759cbeff2ff554fae, f-40c685bb54bc7d7b9ac6b7a5, f-44dadc0f9307c01651d187dc, f-45bdaf4733ac171d7b985d43, f-46ca2827e473e9be80edadba, f-4937df59485334c0c75d2590, f-52d8417a1867893550f0a55a, f-5434d6f82e8d7af43b6b4233, f-54e99fcc15c930cf8d2d6930, f-559b41e947ff8ed90d745067, f-5740b50ce6793047e7956edc, f-593160bfac0efcb49fe31a32, f-5950e7b6a698130e0e00f60d, f-5acf88450ddabc03c59faa51, f-60600ba665c6fe7bc8acf3be, f-6279847889f95ffa1214fc66, f-635571009be3170767dcfa2a, f-70d84131122a6b8a58b97b4b, f-72e84016b3862c3b4d66f492, f-760c0bd024f105a54ed7f304, f-7e36fc058286cce511787914, f-7ee34292391a98369c7da221, f-7f664ba3d8ffa00f7574062c, f-82d45d9bc9faeafb3e48f138, f-898ed2574b16fc250c695fd1, f-89c2ec852bbe2c3b3d6b298d, f-8a96e73675c28d75dbf80f11, f-8f72bebff0dd417cc8b02583, f-91216291bcc303361818ac49, f-912dedba139146913d3f28be, f-92420d9c2121a84f398a4124, f-9347e33900627bffef5a6577, f-96fe331b2b43df135ac035d2, f-9723d1c8d6b91d9afa60ed20, f-984d36298e34384ee5896f7a, f-993e359c15d2e3162d8279a1, f-9e68003bdaadcca474631251, f-a47868218f0714fe7b35d4a6, f-a6e0551fdd966c5a28e8625d, f-a82f40987457c1f9790fc2c9, f-ac8e4810fdf42e684477a9f2, f-afbcdcfe4e299ed68ec34fba, f-b2213cb7a3de1c75c6c8c864, f-bc295857988ae005226a931f, f-bc2e09bf5b428bdf75517603, f-be339e769fc97ab8b2478ee2, f-c259dc11b7cf52ab575340c9, f-c3086e9a3a50a953b469bb54, f-c3ea9e4b5ce922ce7ae3f1f1, f-c4962446536941e9eba5ebdc, f-c6007d77f4debbd36e1cf7c3, f-c617ba415d4a9a810250d78f, f-c66515ded40bea6a5a45c27f, f-c68e61450cd580c7bc40d40a, f-c6a4616847882a7ede8fb13e, f-c7fa43324605611e23a423e0, f-c829a4cb0f87e18460dd55bb, f-c8bf8184e0692aa63e9b7d2f, f-ca61450fcda175795b0b090d, f-cbb25d76b246a5b59e4f0218, f-d262ae7b1e1e12b002ab5b3a, f-d8b509ad0ec1d399ce8b7f48, f-dbd802c4915faa459f9edc8a, f-deeb9791d02e3629d682133e, f-e4d1afa61bbaca87713d8133, f-e986d8f8edecacff5e705f02, f-ea125e60c816bfcd5c112040, f-ed5fd14c418860c77deac594, f-f132eea4ed956f6fec079d4d, f-f6755aa93ddf2d3848f15041, f-f6b85408e42efb260688beb3, f-f94112d2d8689a2e1c3ee929, f-fc0eba755104731f918559d0, f-fd62ced6a49847d6732fc2a3, f-ff06d8e9c7c62e9cd6ae7866

ru · official · sha256:9a038d79cb96408d8f7c3a25278aa9c4273ea4bd02bcbb842b34dba7f69d8085

§5. QR-разложение отражениями Хаусхолдера Задача: по матрице A размера m на n при m не меньше n найти ортогональную Q и верхнетреугольную R, для которых A = Q·R. Вариант — последовательными отражениями Хаусхолдера. Для каждого столбца строится вектор v, отражение по которому обнуляет весь поддиагональный кусок этого столбца. Отражение применяется к оставшейся подматрице. Накопленные отражения дают Q, преобразованная матрица — R. Знак при построении v выбирается СОВПАДАЮЩИМ со знаком ведущего элемента столбца. Противоположный выбор математически допустим и при вычислениях с округлением вызывает потерю значащих цифр вычитанием близких чисел. Это единственное место метода, где выбор знака имеет значение, и опускать его нельзя. Матрица Q обычно не хранится явно: хранятся векторы отражений, а умножение на Q выполняется их последовательным применением. Явное построение Q стоит дополнительной работы и нужно не всегда. Устойчивость: умножение на ортогональную матрицу сохраняет евклидову длину, поэтому погрешность не растёт. Это и есть причина, по которой QR предпочитают методу нормальных уравнений в задаче наименьших квадратов; утверждение принадлежит источнику. Оценка: порядка двух третей куба размера умножений при квадратной матрице, то есть вдвое дороже LU. Дороговизна оплачивается устойчивостью, и обе стороны обязаны называться вместе. Вращения Гивенса решают ту же задачу, обнуляя по одному элементу; они выгодны на разреженных матрицах и составляют другой вариант.

Ссылаются нормы: f-022eb3b7748a5f06758e0eb8, f-059108bd802b0dd9227a6fd5, f-06419da22d2788143f1296f9, f-06b86bf773daca51ac16a954, f-0d1d7b8b3fb4e735520c77a9, f-0f054b8ce9956185fa356e8e, f-0fc36de71da00e6e4e6b9a3b, f-110fa2397fceaf63b057a6fa, f-119c7bde573afdda90f4c047, f-12dcdaedc7c3b76b409c9eb9, f-186eaa8da8a4f26124c9091c, f-1c8a98cddb99606fe5c4d3d6, f-22c29b2bf6fe5b0f624f2a53, f-2543993d089d64b6f0ed23ad, f-255f1634e9b34b1ce747601c, f-28ae73450eee9f209c43c70b, f-2c475521fd111c81da5b1700, f-2d8ffa094411ef4ab38d0afb, f-362d384e6d2f831f5e2f596c, f-372ef4c9de0b4fa033e78867, f-3925f6e0adcd26ee39807b88, f-3ae5d96d2efc14d28868d061, f-3b892e606740e8565d9a7fbc, f-401a03dc86fbc3f23086918a, f-44c7e15de9f43a1a3a4b0a58, f-4a9f443f954bd510d666f3d1, f-4bb33dc0c9c6b1f460f401f6, f-4c53102fd993712c2ff6e37f, f-4dd3630c12a8016f348e4337, f-538d1b017b63662a8e5f3f81, f-5dd493f80f7fd55b3acdb008, f-61d907da01c7bcd88012992f, f-62fbb2480c8dcb712cf68a49, f-63723ad92efda147c6ff33f3, f-6438ab6b998d9d627260ac52, f-6a1be3ed5b0bc418b0ad04e4, f-70d082421415806b2ad49b2b, f-7368aca77fbdc920367d2468, f-7913e39b85a197a9865ab3c3, f-7d52ec9f8d799080f9aa9c78, f-825acfc1f5598bc7c41daaf6, f-85bf285fdc90b7506e5fdc97, f-8902a6702e8fba0cc62dee70, f-8b70b6dd72661834be959f90, f-944cec128eb2a6797d860fe6, f-94ed102f629e03a50fa9ee52, f-972dfa2df368d85078c5614b, f-992000b214088f02a32f1daf, f-a27b10502da08e3acb164e1d, f-a677a58ba9f775a10bddcb7a, f-a81ef90066a5aac011be91ab, f-aaac2c7500e6f26888ebabd0, f-abd5d21aa538fb613cd08046, f-b1ffae61625ee7ed49503cb6, f-b27d4d37db8b05f08281264a, f-b2bfa9ecceefcbc9f2da169c, f-b3c058e9e3b3b7cc4225b8da, f-b3c38f08a91dc8edbcd2bf42, f-b3f55f1d67bd8a04de5c506a, f-b452bfe6edd75490712cdc49, f-b535f60b1de2e763d844dc22, f-b791aefe51fce2378a60abb4, f-b8f728e20b7f23938e769468, f-ba0de4961250bbdcdc4bdd05, f-ba168176ce529fb5f2ead788, f-bb51dbf05b56a30194d1d641, f-c13d724e8224e630f25d0dd7, f-cad06a2475614b0c6b7f193f, f-dab321bf0107f38b94b85b86, f-dac3121b558847d3d37a42ea, f-dc9c75ce5ede8e007bd70cf8, f-df4a4f9426897677be04fa77, f-dfbc9ee0c424c22532e86152, f-e0eb8216d80a0383c5b543a9, f-e4fd2265c383bc8e1a9c89a2, f-e945a08034949c3fd54ba21f, f-eafdf83bb1a19477af7a63d0, f-f0574dbb37c186409489d912, f-f19d42ea66b37f6bfe618931, f-f33f478fb5925c7afeb97587, f-f3682d0b34ff58f4e42de072, f-f45a9803cce2e07841e1f777, f-f6aad4688536055d47f821e7, f-f820ce9557ebbf080f4f7cf5, f-f959bc664ae064dbec1e07be, f-f9a10370baddb9d826621736, f-fd32c677d82a19108f62a083, f-feabb7ad2884a0cf1432e095

ru · official · sha256:3e9fe01ff9431f907de31ece04daaf7d89ac2ed9bf7bda697e469e3bdc3ef342

§6. Обычное умножение матриц Задача: по матрицам A размера m на k и B размера k на n получить произведение C размера m на n, элемент которого есть сумма произведений соответствующих элементов строки A и столбца B. Вариант — тройной цикл по строке, столбцу и общему индексу. Порядок вложения циклов на РЕЗУЛЬТАТ не влияет и влияет только на порядок обращений к памяти; изложение фиксирует порядок «строка, столбец, общий индекс» и говорит, что это выбор изложения, а не требование правильности. Согласованность размеров есть предусловие: число столбцов A обязано равняться числу строк B. Нарушение есть отказ описания, а не ошибка вычисления. Число умножений равно произведению трёх размеров; для квадратных матриц это куб размера. Это утверждение об ОБЫЧНОМ умножении, и именно оно служит моделью стоимости в задаче о порядке перемножения цепочки матриц. Метод Штрассена перемножает две матрицы порядка n за порядка n в степени логарифма семи по основанию два умножений; это ДРУГОЙ алгоритм с другой моделью и другой устойчивостью, и настоящее описание его не воспроизводит. Умножение матриц ассоциативно и не коммутативно. Ассоциативность и есть то, что делает осмысленной задачу о порядке перемножения; некоммутативность — то, из-за чего порядок сомножителей менять нельзя. Исполнимая реализация умножения в репозитории — `calc.matrix`; она владеет представлением матрицы и произведением над ℚ.

Ссылаются нормы: f-00ccbc3d4b7c8f3a5b17a1fd, f-018b378580ef78f485d65a07, f-0bcd06f68fb2b3928782060e, f-0c56e1b435bdcebf1ec6d3b3, f-1282b0e1ecf7e5e651e7e760, f-15831e974ac6a572e33286c7, f-15b97003b14c4d445d6c82dc, f-19645b58f9a9853b1aa402f7, f-20b583aaff508ea7be2bf1ae, f-26ca792834e0a35ba7d0b757, f-2acf5ea7d75279d4454783fe, f-2af09d163ebfb1b4da45afcb, f-2be20bf13c0ff7a43fb944fb, f-2dade5eedeb9aed08f76b60a, f-2ed55a760a6ae834c9ec9ad9, f-308146e8140397b7a647eec6, f-38a69ef7b0602db23c0b72d0, f-3bd08224de96f21ea3266ec1, f-3cc16d786faa516d710cae9f, f-40da5789f58edcb202cf404d, f-4318067302d3cb23df9eafeb, f-444781f3dca6db14663f117a, f-4896b7fead340489bcc0685d, f-58b283664077da4d61a390a9, f-59611d8853951d2761b49871, f-5c72cee14e498e206ce5ab7b, f-601964d8d1a1035346afd34b, f-60302dce588a3229f6428684, f-674b711ab0e88fd550eac8e4, f-6a9a870bf1ff50820a87f118, f-6d9e09fc6492d6f908dea641, f-6dc789b02153d06f7ffb1bf7, f-6ebaf8fba9e2b3ec1f315016, f-7ad2a82de7b71ef640394e6b, f-7da9e1d66e6de4bc7f4df3e5, f-7e905126ebfeaabd4e44995c, f-83020dc831033ae415d9a03c, f-8314953ca78372a9b7f42e81, f-83cdc3faa744c06880704e22, f-84bdaa96254485188911131f, f-87fe2cbbf5857afbffda52e4, f-8b1c58d1871181ca72c75d32, f-8d5b5dc1ef7729d16a074794, f-93139ad43f6ee2d164fca14b, f-a5798275761d610b5b9994b9, f-a5a1562b0b75cdb70e09c1ba, f-aa6baa72d049e2da963b64ed, f-afb1cc607b120be7c90397fa, f-b0a8ee8cef72a2386a73d30e, f-b651697a0d08cc52924c15f7, f-b94adcf816c3614a45fdd775, f-bd12721dc4783b896d2e63e0, f-bdabb62e229759925d160382, f-be9fd3207d094787e083e6b1, f-beaf71d55ea146b176b817d8, f-c06a4b3405bce9d54220afa7, f-c0ab66d5b13ac7f529a73818, f-c0c65e3ce949d0fce6698b61, f-c4c2a7f13b2e21541eab0ee2, f-c6fbbe97cbeb3d405d5f6bfc, f-c7770dfa84f919dd04538999, f-c7d3d54fcc9c12330ec7f2dd, f-cb24bf8f6c2aa3526a8cc6a0, f-ce2d50b4c03f777b215ab5eb, f-cee6ce16169955d7733fe761, f-d1bfcf841ed9131357625e09, f-d248a2c4497fc19228ba137f, f-d6c62b99aa53b45c8347be66, f-db0d5cacd32b290b0e1fb092, f-db175ef7196d73e1c3458e70, f-df0f9a55b62b8ec5ba8606a8, f-e09fb986a758727a3f3e6b8f, f-e13622d29bddca13e47d386d, f-e20c9df1e19a6528fdfe7647, f-e3053849b1d296b28f998d82, f-e5a3f6285b678c7a6acc18f2, f-eafb03898dec49648e1e416d, f-f0fb2f1dc4dd8349b11095a0, f-f10dc4e6274ec9b799e66bae, f-f152eb5851e4bbf68d62c538, f-f45b82eb4594422b7ec7c5a3, f-f720251a0181a01765c80b38, f-f8205195e3667a0ea585a148, f-fcb69e85ff911740959f639d

ru · official · sha256:4c37dd59079de4fbc05c60da5d7cf2fe56f3d6ae4daf3606735eb5af35122837

ЛИНЕЙНАЯ АЛГЕБРА: ИСКЛЮЧЕНИЕ ГАУССА, ГАУСС — ЖОРДАН, LU, QR ОТРАЖЕНИЯМИ И УМНОЖЕНИЕ МАТРИЦ Настоящий документ является АВТОРСКИМ ИЗЛОЖЕНИЕМ, составленным для целей формализации. Он описывает устройство пяти алгоритмов: исключения Гаусса, метода Гаусса — Жордана, LU-разложения с выбором ведущего элемента, QR-разложения отражениями Хаусхолдера и обычного умножения матриц. Изложение не воспроизводит ни один учебник; происхождение каждого алгоритма названо при его описании локатором. Описание отвечает на вопрос об устройстве алгоритма и не выполняет его: ни одна матрица здесь не преобразуется.