Točnost i stabilnost numeričkih algoritama

diplomski rad

• Naslov (engleski): Accuracy and stability of numerical algorithms
• Autor: Matteo Pašić
• Mentor: Nela Bosner (mentor)
• Član povjerenstva: Nela Bosner (predsjednik povjerenstva)
• Član povjerenstva: Eduard Marušić-Paloka (član povjerenstva)
• Član povjerenstva: Josip Tambača (član povjerenstva)
• Član povjerenstva: Matija Bašić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2023-09-27, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U ovom radu smo prvo uveli osnovne pojmove vezane uz QR faktorizaciju, problem najmanjih kvadrata te analizu greške. Uveli smo načine za računanje QR faktorizacije te za rješavanje problema najmanjih kvadrata. Glavni cilj rada je bio napraviti analizu greške svakog od tih načina. Za QR faktorizaciju pomoću Householderovih reflektora te Givensovih rotacija smo prvo krenuli od stabilnosti računanja Householderovim reflektorima, odnosno Givensovim rotacija, te stabilnosti operacija s njima. Pomoću toga smo dokazali glavne rezultate, stabilnost unatrag QR faktorizacije pomoću Householderovih reflektora odnosno Givensovih rotacija. Za metode CGS i MGS smo pokazali da izračunati ortogonalni faktor nije nužno ortogonalan te smo dokazali stabilnost unatrag MGS metode. Za problem najmanjih kvadrata smo prvo dokazali Wedinov perturbacijski teorem te izveli perturbacijske ograde po komponentama. Dokazali smo da su QR faktorizacija pomoću Householderovih reflektora te QR faktorizacija pomoću Givensovih rotacija stabilne unatrag metode za rješavanje problema najmanjih kvadrata. Također smo naveli rezultat da je i MGS metoda stabilan unatrag način za rješavanje unatoč problemima s ortogonalnošću. Za kraj smo neke od ograda, iz rezultata koje smo dokazali, testirali programskim primjerima u MATLAB-u.

Sažetak (engleski)

This thesis firstly introduces basic terms related to QR factorization, least square problem and error analysis. We introduced methods to compute QR factorization and to compute the solution of the least square problem. The main goal of this thesis was to do an error analysis for each of these methods. For Householder and Givens QR factorization, we first proved the stability of the construction and operations with Householder reflectors and Givens rotations. With that we proved our main results, backward stability of Householder and Givens QR factorization. For the CGS and MGS methods we showed that the computed orthogonal factor isn’t necessarily orthogonal and then we proved backward stability for the MGS method. For the least square problem, we first proved Wedin’s perturbation theorem and we derived componentwise perturbation bounds. We proved that Householder and Givens QR factorization provide a backward stable way to solve the least square problem. We also stated that the MGS method provides a backward stable way to solve the least square problem even though its computed orthogonal factor isn’t orthogonal. In the end, we tested some of the bounds we obtained with programmed examples in MATLAB.

• Ključne riječi: QR faktorizacija; najmanji kvadrati; Householderovi reflektori; Givensove rotacije
• Ključne riječi (engleski): QR factorization; least square problem; Householder reflectors; Givens rotations
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:617101
• Studijski program: Naziv: Primijenjena matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: sveučilišni magistar matematike (univ. mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2024-02-05 12:07:20