LU-разложение

LU-разложение (LU-декомпозиция, LU-факторизация) — представление матрицы в виде произведения двух матриц, , где  — нижняя треугольная матрица, а  — верхняя треугольная матрица.

LU-разложение используется для решения систем линейных уравнений, обращения матриц и вычисления определителя. LU-разложение существует только в том случае, когда матрица обратима, а все ведущие (угловые) главные миноры матрицы невырождены[1].

Этот метод является одной из разновидностей метода Гаусса.

Применения

Решение систем линейных уравнений

Полученное LU-разложение матрицы (матрица коэффициентов системы) может быть использовано для решения семейства систем линейных уравнений с различными векторами в правой части[2]:

Если известно LU-разложение матрицы , , исходная система может быть записана как

Эта система может быть решена в два шага. На первом шаге решается система

Поскольку  — нижняя треугольная матрица, эта система решается непосредственно прямой подстановкой.

На втором шаге решается система

Поскольку  — верхняя треугольная матрица, эта система решается непосредственно обратной подстановкой.

Обращение матриц

Обращение матрицы эквивалентно решению линейной системы

,

где  — неизвестная матрица,  — единичная матрица. Решение этой системы является обратной матрицей .

Систему можно решить описанным выше методом LU-разложения.

Вычисление определителя матрицы

Имея LU-разложение матрицы ,

,

можно непосредственно вычислить её определитель,

,

где  — размер матрицы , и  — диагональные элементы матриц и .

Вывод формулы

Исходя из области применения, LU-разложение может быть применено только к невырожденной матрице, поэтому далее будем считать что матрица невырождена.

Поскольку и в первой строке матрицы , и в первом столбце матрицы , все элементы, кроме, возможно, первого, равны нулю, имеем

Если , то или . В первом случае целиком состоит из нулей первая строка матрицы , во втором — первый столбец матрицы . Следовательно, или вырождена, а значит, вырождена , что приводит к противоречию. Таким образом, если , то невырожденная матрица не имеет LU-разложения.

Пусть , тогда и . Поскольку столбец L и строка U определены с точностью до умножения строки U на константу и деления столбца L на ту же константу, мы можем потребовать, чтобы . При этом .

Разделим матрицу A на клетки:

,

где имеют размерность соответственно , , .

Аналогично разделим на клетки матрицы и :

Уравнение принимает вид

Решая систему уравнений относительно , , , , получаем:

Окончательно имеем:

Итак, мы свели LU-разложение матрицы размера к LU-разложению матрицы размера .

Выражение называется дополнением Шура элемента в матрице A[1].

Алгоритм

Один из алгоритмов для вычисления LU-разложения приведён ниже.[3]

Будем использовать следующие обозначения для элементов матриц: , , , ; причём диагональные элементы матрицы : , .

Найти матрицы и можно следующим образом (выполнять шаги следует строго по порядку, так как следующие элементы находятся с использованием предыдущих):

  1. Цикл i от 1 до n
    1. Цикл j от 1 до n
      1. uij=0, lij=0
    2. lii=1
  2. Цикл i от 1 до n
    1. Цикл j от 1 до n
      1. Если i<=j:
      2. Если i>j:

В итоге мы получим матрицы — и .

См. также

Примечания

  1. 1 2 Е. Е. Тыртышников. Матричный анализ и линейная алгебра. — 2004-2005.
  2. Левитин, 2006.
  3. Вержбицкий В.М. Основы численных методов. Учебник для вузов. — Высшая школа, 2002. — С. 63-64. — ISBN 5-06-004020-8.

Литература

Read other articles:

ライアン・タネヒルRyan Tannehill テネシー・タイタンズでのタネヒル(2021年)テネシー・タイタンズ #17ポジション クォーターバック生年月日 (1988-07-27) 1988年7月27日(35歳)出身地 アメリカ合衆国テキサス州ラボック身長: 6' 4 =約193cm体重: 217 lb =約98.4kg経歴高校 ビッグ・スプリング高等学校大学 テキサスA&M大学NFLドラフト 2012年 / 1巡目全体8位所属歴 2012-2018 マイアミ

 

Hitorijime My Heroひとりじめマイヒーロー(Hitoriji me Maihīrō)GenreRomansa MangaPengarangMemeco AriiPenerbitIchijinshaPenerbit bahasa InggrisNA Kodansha USAMajalahGateauTerbitFebruari 2012 – sekarangVolume14 Seri animeSutradaraYukina HiiroSkenarioYūsei NaruseMusikTakeshi SenooMitsutaka TajiriStudioEncourage FilmsPelisensiNA Sentai FilmworksSaluranasliAT-X, Tokyo MX, BS NTVTayang 8 Juli 2017 – 23 September 2017Episode12  Portal anime dan manga Hitorijime My Hero (Jepa...

 

Savagnier Ort Reformert kyrka i Savagnier Heraldiskt vapen Land  Schweiz Kanton Neuchâtel Kommun Val-de-Ruz Höjdläge 750 m ö.h. Koordinater 47°3′1″N 6°57′24″Ö / 47.05028°N 6.95667°Ö / 47.05028; 6.95667 Yta 6,16 km²[1] Folkmängd 1 149 (2021-12-31)[2][a] Befolkningstäthet 187 inv./km² Tidszon CET (UTC+1)  - sommartid CEST (UTC+2) Postnummer 2065 Savagnier Tidigare kommunkod 6484 (–2013)[3] Geonames 2658...

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (أغسطس 2021) كوخ بن غوريونالتسميةنسبة الاسم إلى دافيد بن غوريون معلومات عامةنوع المبنى متحف — سقيفة المكان سديه بوكير العنوان שדה בוקר (بالعبرية) المنطقة الإدارية سديه ...

 

До списку держав Стародавнього світу віднесено держави, що існували у період від найдавніших часів до 476 року н. е. (занепад Західної Римської імперії), що в Європі традиційно вважається кінцем Стародавнього світу і початком Середньовіччя. Список відсортований у алфав...

 

Trường Đại học Hòa BìnhĐịa chỉ8 phố Bùi Xuân Phái, phường Mỹ Đình 2, quận Nam Từ Liêm, Hà Nội, Việt NamThông tinLoạiĐại học dân lậpKhẩu hiệuNâng cánh bay xaThành lập28 tháng 2 năm 2008Hiệu trưởngNGND.PGS.TS. Tô Ngọc HưngWebsitedaihochoabinh.edu.vn, Trang tuyển sinhTổ chức và quản lýPhó hiệu trưởngGS.TS. Đào Văn Đông GS.TS. Trần Trung TS. Đào Hải Lịch sử hình thành Trường Đại học Hoà B...

此條目或章節為有关籌備中,拍攝中或待播的電視節目。未有可靠来源的臆測內容可能會被移除。目前記載或許與實際節目播出之內容有所出入,亦可能會隨節目的播出而變化並增添更多有效信息。 法證先鋒6 倖存者的救贖Forensic Heroes 6类型時裝懸疑查案[來源請求]编剧方世強(總編審)[1]、葉泳洪、周俊傑[來源請求]主演黃宗澤、袁偉豪、蔡潔、蔣祖曼、傅

 

American television series This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: The Hogan Family – news · newspapers · books · scholar · JSTOR (February 2020) (Learn how and when to remove this template message) The Hogan FamilyOriginal cast from 1986-87Also known asValerie (1986–1987)Valerie's Family: The Hoga...

 

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: The Seven Deadly Sins 1962 film – news · newspapers · books · scholar · JSTOR (February 2020) (Learn how and when to remove this template message) 1962 filmLes Sept péchés capitauxDirected byPhilippe de Broca Claude Chabrol Jacques Demy Sylvain Dhomme Ma...

Third period of the Paleozoic Era, 443–419 million years ago Not to be confused with Silurian (Doctor Who). For other uses, see Silurian (disambiguation). Silurian443.8 ± 1.5 – 419.2 ± 3.2 Ma PreꞒ Ꞓ O S D C P T J K Pg N Map of Earth during the early Silurian, c. 440 MaChronology−444 —–−442 —–−440 —–−438 —–−436 —–−434 —–−432 —̵...

 

Language of Nigeria EfikUsem EfịkNative toSouthern NigeriaRegionCross River StateEthnicityEfikNative speakers698 620 (2020)[1]Second language: 2 million[1]Language familyNiger–Congo? Atlantic–CongoVolta-CongoBenue–CongoCross RiverLower CrossEfik-IbibioEfikWriting systemLatinNsibidiLanguage codesISO 639-2efiISO 639-3efiGlottologefik1245 Efik /ˈɛfɪk/ EF-ik[2] (Usem Efịk) is the indigenous language of the Efik people, who are situated in the present...

 

American college football season 1998 VMI Keydets footballConferenceSouthern ConferenceRecord1–10 (0–8 SoCon)Head coachTed Cain (2nd season; first 10 games)Donny White (interim, last game)Home stadiumAlumni Memorial Field(capacity: 10,000)Seasons← 19971999 → 1998 Southern Conference football standings vte Conf Overall Team   W   L     W   L   No. 2 Georgia Southern $^   8 – 0     14 – 1   No....

9П149 Боевая машина 9П149 в Минске 9П149 Классификация самоходный противотанковый комплекс Боевая масса, т 12,3[1] Экипаж, чел. 2 История Производитель Годы разработки 1970-е Годы производства с 1978 Годы эксплуатации с 1979 Количество выпущенных, шт. более 1000 Основные операторы Ра...

 

Radio 4Wilayah siarNetherlandsMulai mengudara1975Formatmusik klasikKode panggil sebelumnyaHilversum 4PemilikPublieke_OmroepSitus webwww.radio4.nl Radio 4 adalah sebuah jaringan radio publik NPO di Belanda, siaran musik utama mereka adalah musik klasik. Radio 4 mulai dimulai pada tanggal 28 Desember tahun 1975 dengan nama Hilversum 4. Asosiasi penyiaran saat ini menyediakan program di Radio 4: AVRO, KRO, MAX, NCRV, NTR, TROS, VARA, VPRO. Awalnya, stasiun dioperasikan hanya selama malam hari, t...

 

American-bred Thoroughbred racehorse For other uses, see Zenyatta (disambiguation). ZenyattaZenyatta winning the Lady's Secret StakesSireStreet CryGrandsireMachiavellianDamVertigineuxDamsireKris S.SexMareFoaled (2004-04-01) April 1, 2004 (age 19)Lexington, Kentucky, U.S.CountryUnited StatesColourDark Bay/BrownBreederMaverick Productions, LimitedOwnerJerry & Ann MossTrainerJohn ShirreffsJockeyMike SmithRecord20: 19–1–0Earnings$7,304,580[1]Major winsEl Encino Stakes (2008)A...

Catholic charitable organization Caritas Bangladeshকারিতাস বাংলাদেশPredecessorCaritas PakistanFormation1967; 56 years ago (1967) (as Caritas East Pakistan)TypeNonprofit, NGOLegal statuscharityFocusHumanitarian aid, International development and social serviceHeadquarters2, Outer Circular Road, ShantibaghLocationDhaka, BangladeshRegion served BangladeshPresidentGervas RozarioVice PresidentTheotonius P. RebeiroParent organizationCaritas Internatio...

 

Кириченко Ілля Олександрович  Солдат Загальна інформаціяНародження 30 березня 1988(1988-03-30)Жовті Води, Дніпропетровська область, УРСРСмерть 10 червня 2017(2017-06-10) (29 років)Кримське, Луганська область, Україна(мінометний обстріл)Військова службаРоки служби 2017Приналежність ...

 

Breakfast cereal made by MOM Brands This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Marshmallow Mateys – news · newspapers · books · scholar · JSTOR (August 2010) (Learn how and when to remove this template message) Marshmallow Mateys Marshmallow MateysNutritional value per 130 gEnergy120 kcal (500...

2011 novel by Orson Scott Card The Lost Gate First edition book cover (Hardback)AuthorOrson Scott CardCountryUnited StatesLanguageEnglishSeriesThe Mither MagesGenreFantasyPublisherTor BooksPublication dateJanuary 4, 2011Media typePrint (hard-cover, softcover) and Audio bookPages384ISBN978-0-7653-2657-7Followed byThe Gate Thief  The Lost Gate is a fantasy novel by Orson Scott Card. It is the first novel in the Mither Mages trilogy. The second novel is The Gate Thief and the thir...

 

High Court of New Zealand case This article is an orphan, as no other articles link to it. Please introduce links to this page from related articles; try the Find link tool for suggestions. (September 2015) Oxborough v North Harbour Builders LtdCourtHigh Court of New ZealandFull case nameAndrew & Gaye Oxborough v North Harbour Builders Ltd & Regency Designer Homes Ltd Decided29 March 2001Transcript(s)High Court judgmentCourt membershipJudge(s) sittingNicholson J Oxborough v North Harb...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!