Akademik Veri Yönetim Sistemi
Tezin Türü: Yüksek Lisans
Tezin Yürütüldüğü Kurum: Marmara Üniversitesi, Fen Bilimleri Enstitüsü, Türkiye
Tezin Onay Tarihi: 2019
Tezin Dili: İngilizce
Öğrenci: OSMAN MECNUN DURU
Danışman: Onur Cihan
Özet:ÖZETÇE DOĞRUSAL DENKLEMLERİN ÇÖZÜMÜ İÇİN KULLANILAN DAĞITIK BİR ALGORİTMANIN ANALİZİ Doğrusal bir denklem sistemini çözmek, bilim ve mühendislikteki en bilinen ve en önemli sorunlardan biridir. Bu tarz sistemlerin, öngörme, kestirim ve doğrusal olmayan denklemlerin doğrusal yaklaşımları gibi sayısız uygulamaları vardır. Bu sistemlerin çözümü için literatürde, büyük doğrusal denklem sistemlerini küçük parçalara bölen ve merkezi bir işlemci ile çözmekten daha hızlı ve daha doğru bir şekilde çözülmelerini sağlayan çeşitli dağıtık algoritmalar önerilmiştir. Bu algoritmaların temel fikri, sistemi, özerk etmenlerin birbirlerinden fiziksel olarak ayrıldığı ve yakındaki komşularıyla iletişim kurduğu çok etmenli bir ağ yapısı olarak görmektir. Ağ, her bir etmenin sadece denklemin bir alt kümesini bildiği birden fazla etmenden oluşur ve bu nedenle hiçbiri toplam denklemi ayrı ayrı çözemez.. Bu sorunun üstesinden gelmek için, tüm etmenler dağıtık bir şekilde işbirliği içinde çalışmalıdır. Her i etmeninin R^n de değerler alan bir çözüm vektörü x_i (t) vardır ve etmen i nin komşusu j den aldığı tek bilginin, onun durum vektörü olduğu varsayılmaktadır. Bu tezin amacı, doğrusal cebirsel denklem kümesini çözmek için [1]’de önerilen dağıtık algoritmayı geliştirmek ve yakınsama oranını araştırmaktır. Bu tezde, dağıtık bir algoritma ele alınmış ve iletim gecikmeleri olan ve olmayan ağlardaki yakınsaklık oranları incelenmiştir. Her iki durum için yeni ve hızlı bir yöntem önerilmiştir. Literatürdeki iyi bilinen bir algoritmanın yakınsama oranı ve bu tezde önerilen algoritmanın yakınsama oranı gecikmesiz ve gecikmeli ağlar için karşılaştırılmıştır. Ayrıca, ağırlıklandırma yöntemlerinin algoritmanın yakınsama oranı üzerindeki etkisi de birkaç önemli ağ topolojisi için incelenmiştir ve ele alınan tüm topolojiler için, rastgele yürüyüş yönteminin, örnek denklem sistemi için en hızlı yakınsamayı sağladığı gösterilmiştir. -------------------- ABSTRACT ANALYSIS OF A DISTRIBUTED ALGORITHM FOR SOLVING LINEAR EQUATIONS Solving a linear equation system is one of the most known and important problems in science and engineering. Such systems have numerous applications such as forecasting, estimation and linear approaches to nonlinear equations. For the solution of these systems, several distributed algorithms have been proposed in the literature, which divide large linear equation systems into small pieces and enable them to be solved faster and more accurately than solving it by a centralized processor. The basic idea of these algorithms is to consider the system as a multi-agent network structure where the autonomous agents are physically separated from each other and communicate with their neighbors nearby. The network consists of multiple agents, each agent knows only a subset of the equation and therefore none can solve the overall equation individually. In order to overcome this issue, all agents must work cooperatively in a distributed way. Each agent i has a solution vector x_i (t) that takes values in R^n, and it is assumed that the only information that the agent receives from its neighbor j is its state vector. The aim of the thesis is to upgrade a well-known distributed algorithm in [1] for solving a linear algebraic equation and investigate its convergence rate. In this thesis, we consider a distributed algorithm and examine its convergence rate in networks with and without transmission delays. A new rapid method is proposed for both cases. Convergence rates of a well-known algorithm in the literature and the one proposed in this thesis are compared for un-delayed and delayed networks. Furthermore, the effect of weighting strategies on the convergence rate of the algorithm is investigated for several important network topologies as well and it is shown that for all topologies under consideration, the random walk method yields the fastest convergence for the example equation system.