Točnost i stabilnost numeričkih algoritama

master's thesis

• Title (english): Accuracy and stability of numerical algorithms
• Author: Matteo Pašić
• Mentor: Nela Bosner (mentor)
• Committee member: Nela Bosner (predsjednik povjerenstva)
• Committee member: Eduard Marušić-Paloka (član povjerenstva)
• Committee member: Josip Tambača (član povjerenstva)
• Committee member: Matija Bašić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2023-09-27, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: QR faktorizacija; najmanji kvadrati; Householderovi reflektori; Givensove rotacije
• Keywords (english): QR factorization; least square problem; Householder reflectors; Givens rotations
• Language: croatian
• URN:NBN: urn:nbn:hr:217:617101
• Study programme: Title: Applied Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: sveučilišni magistar matematike (sveučilišni magistar matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2024-02-05 12:07:20