Métodos tipo simplex são a base dos principais softwares utilizados na resolução de problemas de otimização linear. A implementação computacional direta destes métodos, assim como são descritos na teoria, leva a resultados indesejáveis na resolução de problemas reais de grande porte. Assim, a utilização de técnicas computacionais adequadas é fundamental para uma implementação eficiente e estável. Neste trabalho, as principais técnicas são discutidas, com enfoque naquelas que buscam proporcionar a estabilidade numérica do método: utilização de tolerâncias, estabilização do teste da razão, mudança de escala e representação da matriz básica. Para este último tópico, são apresentadas duas técnicas, a Forma Produto da Inversa e a Decomposição LU. A análise das abordagens é feita baseando-se na resolução dos problemas da biblioteca Netlib / Simplex-type methods are the basis of the main linear optimization solvers. The straightforward implementation of these methods as they are presented in theory yield unexpected results in solving reallife large-scale problems. Hence, it is essencial to use suitable computational techniques for an efficient and stable implementation. In this thesis, we address the main techniques focusing on those which aim for numerical stability of the method: use of tolerances, stable ratio test, scaling and representation of the basis matrix. For the latter topic, we present two techniques, the Product Form of Inverse and the LU decomposition. The Netlib problems are solved using the approaches addressed and the results are analyzed

Made available in DSpace on 2015-05-14T12:09:19Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 8337458 bytes, checksum: 6418a75dca756790257aecdb25414305 (MD5) Previous issue date: 2013-05-10 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / The SRTM-DEM has been widely used for deriving drainage networks and for several different environmental studies. However, sometimes it is not possible to work with the original spatial resolution of the available DEM, mainly when the study area is large owing to the increase in computational cost, requiring the DEM to be resampled to a coarse resolution. According to the method used for deriving coarse-resolution drainage networks, the quality of the result can be quite different. The wrong choice of the method together with the inherent loss of information within this process may result in a river drainage network incoherent relative to an available network considered as correct. For this reason, this research aimed at identifying the errors present in flow paths and in the physical characteristics of four large-scale watersheds (Paraíba (20.000 km2), São Francisco (640.000 km2), Tapajós (500.000 km2) and Uruguai (207.000 km2)) and its major tributaries in both qualitative and quantitative ways. The comparisons between the drainage networks extracted from DEMs with different spatial resolutions and using different methods (DEM resampling, direct upscaling, multi-step upscaling) were carried out relatively to a high-resolution drainage network obtained from processing the original SRTM-DEM for the qualitative analysis, while for the quantitative analysis the drainage network manually digitized over ETM+/ LANDSAT 7 satellite images was used. The flow paths obtained through the methods of DEM resampling showed strong incoherencies mostly when the change in scale was large, and these errors influenced the area and shape of watersheds and also the quality of the derived drainage network, being stronger for the larger watersheds. The drainage networks obtained through the flow directions upscaling were of better quality because they reproduced more closely the high-resolution network. The multi-step upscaling method showed the better performance for three of the four study areas. The quantitative analysis relative to area and mean distance measured between the DEM-derived drainage network and that one obtained from LANDSAT images showed to be coherent to the qualitative analysis, indicating the multi-step upscaling method as the one of better performance, and the resampling procedure as the worst one. The results in terms of watershed areas comparison were coherent to the visual inspection, showing that the upscaling process reproduced quite well the values obtained in the high resolution, both quantitatively and qualitatively. The direct upscaling procedure obtained the best performance while the resampling method resulted in the largest inconsistencies regarding these two aspects, resulting in watershed delimitation totally different from the actual, mostly for Sao Francisco and Tapajos watersheds, in which the change in scale was larger. The influence of the methods used and of the change in scale over the length and sinuosity of river reaches was detected, sometimes resulting that the result was not very well presented. This can be highlighted when the numerical analysis is compared to the qualitative analysis for results obtained with the resampling procedure. However, although inconsistencies were presented for some river reaches, the upscaling procedure was able to have the largest number of river reaches with the best results. It can be concluded that independent on the characteristics of the watershed to be studied, the resampling procedure is not an adequate method for obtaining coarse-resolution drainage networks. The flow directions upscaling procedure is the most recommend method to be used in this situation, and the multi-step version of this method is the one with best performance when evaluating the flow paths for the study cases of this research. / O MDE do SRTM tem sido largamente utilizado na derivação da rede drenagem e aplicado a diversos tipos de estudos ambientais. No entanto, muitas vezes não é possível trabalhar com a sua resolução original. Isso ocorre quando o estudo é aplicado a grandes áreas e devido ao elevado processamento computacional é necessário a mudança de escala para baixa resolução. Dependendo do método utilizado para a derivação da rede de drenagem obtida de baixa resolução, pode-se adquirir um produto de melhor ou de pior qualidade. A escolha incorreta do método aliada a perda de informação existente nesse processo pode resultar em uma rede incoerente quando comparada a uma rede de drenagem considerada como referência. Esta pesquisa identificou erros nos traçados e nas características físicas de quatro bacias hidrográficas (Paraíba (20.000 km2), São Francisco (640.000 km2), Tapajós (500.000 km2) e Uruguai (207.000 km2)) e nos seus principais afluentes de forma qualitativa e quantitativa. As comparações das redes extraídas das imagens do SRTM em diferentes escalas e métodos (reamostragem, upscaling direto, upscaling gradual) foram realizadas em relação à rede de drenagem de alta resolução obtida do MDE para as análises qualitativas e para as comparações quantitativas com a rede vetorizada das imagens do ETM+/ LANDSAT 7. Verificou-se que os traçados da drenagem obtidos por reamostragem apresentaram várias incoerências principalmente quando a mudança de escala foi maior, esses erros refletiram sobre área, formato de bacias e traçados da rede de drenagem. Os erros foram mais graves nas bacias de maior área de drenagem. Já as redes de drenagem obtidas por upscaling de direções de fluxo foram de melhor qualidade para mudança de escala por essas se apresentarem mais coerentes com a drenagem de alta resolução. O método de upscaling gradual foi o que apresentou melhor desempenho em três bacias das quatro analisadas. As análises quantitativas referentes a área e distância média entre as redes de drenagem, extraída do MDE, e a vetorizada da imagem LANDSAT, apresentaram-se coerentes com as análises qualitativas, apontando o método de upscaling de direções de fluxo na modalidade gradual com melhor desempenho e o método de reamostragem com os piores resultados. Observou-se que as áreas das bacias mostraram-se coerentes com a análise visual, indicando que os métodos de upscaling nas modalidades direta e gradual se aproximaram mais das bacias de alta resolução e apresentaram valores muito próximos entre si, tanto qualitativamente quanto quantitativamente. A modalidade direta de upscaling foi a que apresentou melhor desempenho e o procedimento de reamostragem foi o que apresentou mais incoerências. Por se descaracterizar das bacias de referência, principalmente para o São Francisco e Tapajós para as quais se trabalhou com mudança de escala maior. Percebeu-se que a influência dos métodos e da mudança de escala sobre os valores dos comprimentos e sinuosidade dos rios, algumas vezes repercutiram sobre a métrica gerada não conseguindo expressar a real qualidade da rede de drenagem analisada, mascarando o resultado. Isso pode ser evidenciado quando confrontado a análise estatística e a qualitativa para o método de reamostragem. No entanto, apesar de encontrar alguns rios com essas incoerências, os upscaling direto e gradual conseguiram apresentar um maior número de rios com melhor desempenho. Conclui-se que independente das características das bacias estudadas, o método de reamostragem do MDE não é o procedimento mais adequado na obtenção de redes de drenagem de baixa resolução espacial. O método de upscaling de direções de fluxo nas modalidades direta e gradual são mais indicados para essa finalidade, sendo o gradual o que apresentou melhor desempenho na avaliação dos traçados para as bacias estudadas nesta pesquisa.

Métodos tipo simplex são a base dos principais softwares utilizados na resolução de problemas de otimização linear. A implementação computacional direta destes métodos, assim como são descritos na teoria, leva a resultados indesejáveis na resolução de problemas reais de grande porte. Assim, a utilização de técnicas computacionais adequadas é fundamental para uma implementação eficiente e estável. Neste trabalho, as principais técnicas são discutidas, com enfoque naquelas que buscam proporcionar a estabilidade numérica do método: utilização de tolerâncias, estabilização do teste da razão, mudança de escala e representação da matriz básica. Para este último tópico, são apresentadas duas técnicas, a Forma Produto da Inversa e a Decomposição LU. A análise das abordagens é feita baseando-se na resolução dos problemas da biblioteca Netlib / Simplex-type methods are the basis of the main linear optimization solvers. The straightforward implementation of these methods as they are presented in theory yield unexpected results in solving reallife large-scale problems. Hence, it is essencial to use suitable computational techniques for an efficient and stable implementation. In this thesis, we address the main techniques focusing on those which aim for numerical stability of the method: use of tolerances, stable ratio test, scaling and representation of the basis matrix. For the latter topic, we present two techniques, the Product Form of Inverse and the LU decomposition. The Netlib problems are solved using the approaches addressed and the results are analyzed