Prévia do material em texto
M A RIN A V A RG A S MARINA VARGAS M A TEM Á TICA PA RA CO M PUTA Çà O M A T E M Á T I C A COMPUTAÇÃO PARA Código Logístico I000122 ISBN 978-65-5821-071-9 9 7 8 6 5 5 8 2 1 0 7 1 9 M A RIN A V A RG A S MARINA VARGAS M A TEM Á TICA PA RA CO M PUTA Çà O M A T E M Á T I C A COMPUTAÇÃO PARA Código Logístico I000122 ISBN 978-65-5821-071-9 9 7 8 6 5 5 8 2 1 0 7 1 9 Matemática para Computação Marina Vargas IESDE BRASIL 2021 © 2021 – IESDE BRASIL S/A. É proibida a reprodução, mesmo parcial, por qualquer processo, sem autorização por escrito da autora e do detentor dos direitos autorais. Projeto de capa: IESDE BRASIL S/A. Imagem da capa: whiteMocca/majcot/Lantica/Shutterstock Todos os direitos reservados. IESDE BRASIL S/A. Al. Dr. Carlos de Carvalho, 1.482. CEP: 80730-200 Batel – Curitiba – PR 0800 708 88 88 – www.iesde.com.br CIP-BRASIL. CATALOGAÇÃO NA PUBLICAÇÃO SINDICATO NACIONAL DOS EDITORES DE LIVROS, RJ V427m Vargas, Marina Matemática para computação / Marina Vargas. - 1. ed. - Curitiba [PR] : Iesde, 2021. 160 p. : il. Inclui bibliografia ISBN 978-65-5821-071-9 1. Computação - Matemática. 2. Programação (Computadores). 3. Algoritmos. 4. Matrizes (Matemática). I. Título. 21-72772 21-72772 CDD: 518.1 CDU: 519.165:004.021 Marina Vargas Pós-doutora em Mecânica Computacional pela Universidade Federal do Paraná (UFPR). Doutora e mestre em Métodos Numéricos em Engenharia pela UFPR. Especialista em Educação Matemática e licenciada em Matemática pela Universidade Paranaense (Unipar). Professora no ensino superior nas modalidades presencial e a distância, ministra as disciplinas Cálculo de Funções de uma e mais Variáveis, Álgebra Linear, Geometria Analítica, Métodos Numéricos, Teoria dos Números, Pesquisa Operacional, Matemática Aplicada, Estatística Aplicada e Métodos Quantitativos. Atua também como professora conteudista em diversas instituições e empresas. Atualmente, desenvolve pesquisas nas áreas de programação matemática, mecânica computacional, educação matemática e educação em engenharias. SUMÁRIO Agora é possível acessar os vídeos do livro por meio de QR codes (códigos de barras) presentes no início de cada seção de capítulo. Acesse os vídeos automaticamente, direcionando a câmera fotográ�ca de seu smartphone ou tablet para o QR code. Em alguns dispositivos é necessário ter instalado um leitor de QR code, que pode ser adquirido gratuitamente em lojas de aplicativos. Vídeos em QR code! SUMÁRIO Agora é possível acessar os vídeos do livro por meio de QR codes (códigos de barras) presentes no início de cada seção de capítulo. Acesse os vídeos automaticamente, direcionando a câmera fotográ�ca de seu smartphone ou tablet para o QR code. Em alguns dispositivos é necessário ter instalado um leitor de QR code, que pode ser adquirido gratuitamente em lojas de aplicativos. Vídeos em QR code! 1 Por que estudar matemática? 9 1.1 O que é matemática computacional 9 1.2 Idealização de um algoritmo numérico 15 1.3 Relações de recorrência 19 1.4 Conceito de função no aspecto computacional 22 1.5 Diferenças entre problemas qualitativos e quantitativos 24 2 Noções sobre sistemas de numeração 29 2.1 Sistemas de numeração 29 2.2 Representação numérica 35 2.3 Representação em ponto flutuante 43 2.4 Erros numéricos 46 3 Matrizes 54 3.1 Vetores de uma matriz 55 3.2 Análise do algoritmo padrão para multiplicação de matrizes 58 3.3 Bases 61 3.4 Fatoração matricial – Método de Gauss 64 3.5 Decomposição LU e LDU 69 3.6 Inversa de uma matriz 75 4 Sistemas de equações lineares 81 4.1 Sistemas equivalentes e operações 82 4.2 Sistemas triangulares e escalonados 86 4.3 Eliminação gaussiana 94 4.4 Condicionamento de sistemas lineares 101 4.5 Métodos iterativos 108 5 Grafos e árvores 123 5.1 O que é um grafo: terminologia e tipos 124 5.2 Representação computacional de um grafo 132 5.3 Conceito de árvore 138 5.4 Raízes e árvores binárias 142 5.5 Introdução a procedimentos de busca 145 Resolução das atividades 150 Nesta obra, buscamos trazer os conceitos básicos da matemática para o trabalho, não só com algoritmos a serem implementados nas mais diversas linguagens de programação, mas, principalmente, a lógica por trás dos cálculos computacionais. Quando mencionamos cálculos computacionais, além de pensarmos a forma como a máquina opera e, portanto, trabalha com sistemas de numeração, erros numéricos e vetores, é necessário falarmos de conceitos, como sistemas em rede e grafos, pois estes estão diretamente relacionados às teorias mais atuais da computação, como inteligência artificial, redes neurais etc. Desse modo, destinamos o primeiro capítulo a apresentar um pouco da história do desenvolvimento da computação, que está diretamente ligada ao desenvolvimento da matemática. Apresentamos alguns dos nomes importantes dessa história e mostramos suas contribuições para a matemática computacional. Além disso, contextualizamos conceitos como algoritmo e relações de recorrência e tratamos da diferença entre problemas qualitativos e quantitativos. No segundo capítulo, discorremos sobre os sistemas de numeração aditivos e posicionais, destacando o sistema de numeração posicional decimal, relacionando-o com o sistema por trás das máquinas eletrônicas: o sistema posicional binário. Também trabalhamos o conceito de erro entre o resultado esperado e o resultado encontrado. Para esse fim, construímos um fluxograma que mostra, com base em um modelo real, as ramificações possíveis até que seja obtida a solução numérica/computacional desejada. A proposta do Capítulo 3 é a explanação sobre os conceitos de vetores e matrizes e as operações que os representam. Essa escolha se dá pela facilidade em operar computacionalmente por meio dessas estruturas matemáticas. Assim, seu entendimento é essencial para a matemática computacional. Além disso, trabalhamos com a decomposição de matrizes, preparando caminho para o tema do próximo capítulo. APRESENTAÇÃOVídeo 8 Matemática para Computação Nesse contexto, entramos no quarto capítulo, que trata dos sistemas de equações e visa trazer técnicas numéricas e algoritmos que permitam a implementação computacional desses sistemas. Podemos exemplificar essa necessidade por meio de uma extensa lista de aplicações, entre elas: redes de computadores, resolução de modelos que representam fenômenos físicos e gerenciamento de sistemas. No entanto, além desse contexto, elas podem ser diretamente aplicadas ao próximo capítulo, que aborda os grafos. O Capítulo 5 apresenta a concepção de grafo. Por intermédio de um grafo, podemos representar problemas aplicados e identificar situações em que a busca por um caminho mínimo não só agiliza processos, mas também minimiza custos. Para essa construção, retomamos o uso de matrizes e vetores, sendo essa uma importante forma de implementação desse conceito. É fácil notarmos que os três últimos capítulos têm uma conexão importante dentro da matemática computacional e se comunicam com a computação de maneira quase que natural. Esse é um dos fatores para que esses conceitos estejam em todos os melhores cursos de computação e tecnologia da informação com todas as suas ramificações. Este é o foco desta obra. Nossa proposta é trazer o raciocínio lógico matemático por trás da necessidade de implementação computacional de problemas aplicados na área da tecnologia da informação e computação. Esperamos que este livro auxilie no aprendizado para a formação de um melhor profissional na área escolhida. Bons estudos! Por que estudar matemática? 9 1 Por que estudar matemática? A matemática está por trás da lógica de programação de uma maneira que você talvez nunca tenha parado para pensar. A ciência da programa- ção começou por intermédio de matemáticos curiosos e muito à frente de seus tempos, que tentavam otimizarprocessos e avançar com a possibi- lidade dos cálculos serem realizados por máquinas. A ideia era que essas máquinas recebessem mais do que números, ou seja, que pudessem re- ceber instruções. E eles conseguiram! Neste capítulo, destinado ao estudo da ligação da matemática com a computação, vamos conhecer um pouco da história desses matemáticos e compreender por que é tão importante conhecer matemática para dis- cutirmos sobre computação. Com o estudo deste capítulo, você será capaz de: • compreender a matemática por trás de conceitos computacionais; • reconhecer a diferença entre matemática teórica e matemá- tica computacional; • identificar o uso de cálculos numéricos por trás de algoritmos; • relacionar o conceito de função em diferentes realidades computacionais; • compreender as dimensões quantitativas de um problema. Objetivos de aprendizagem 1.1 O que é matemática computacional Vídeo Quando pensamos em matemática computacional, precisamos en- tender, em primeiro lugar, como um “computador” faz cálculos. Aqui, estamos chamando de “computador” todos os objetos que são capazes de realizar cálculos discretos, como: calculadoras, computadores, celu- 10 Matemática para Computação lares, dentre outros. Assim, todos os objetos que utilizam o princípio de abertura e fechamento de chaves e que permitem ou não a passagem de energia serão analisados perante a mesma lógica de construção para obtenção da chamada matemática computacional. Quando escrevemos os cálculos, percebemos que eles serão reali- zados usando um princípio mecânico básico de abertura e fechamento de chaves, e que estamos envolvendo nesse processo uma lógica bi- nária. Essa lógica precisa ser processada e interpretada. É nesse ponto que entram os diferentes hardwares de processamento e, em conjun- to, os softwares que interpretam esses dados processados. É justamente por esse desenvolvimento que começamos a identifi- car a existência de erros numéricos, os quais podem surgir no processo de cálculo. Além disso, é por meio da lógica binária que identificamos o teor discreto da matemática computacional. Agora vamos conhecer alguns dos nomes que permitiram que a ma- temática computacional acontecesse. 1.1.1 Ada Lovelace Augusta Ada Byron King, Condessa de Lovelace, nasceu em 10 de dezembro de 1815 na cidade de Londres e faleceu em 27 de novembro de 1852, aos 36 anos, no bairro Marylebone, na mesma cidade em que nasceu, na Inglaterra. Ada Lovela- ce é conhecida como a primeira programadora da história. Ela viveu em uma época em que as mulheres não eram bem-vistas em universidades. Por esse motivo, e com estímulo de sua mãe (Anne Isabella “Anabella” Byron, Baro- nesa de Wentworth), Ada estudou em casa com tutores como Augustus De Morgan e Mary Sommerville, que se tornou não apenas sua tutora, mas sua amiga (BIM, 2018). Foi Sommerville quem apresentou Ada ao cientista Charles Babba- ge (1791-1871), matemático, conhecido por ter criado a primeira má- quina capaz de resolver e imprimir cálculos matemáticos. A invenção, chamada de máquina analítica (Figura 1), é considera- da precursora dos computadores modernos (BROMLEY, 1982). Ada Lovelace Ke lso n/W ikim edia Comm ons Por que estudar matemática? 11 Charles Babbage Connormah/Wikimedia Commons Figura 1 Réplica da máquina analítica Br un o Ba rra l/W ik im ed ia C om m on s Mas foi Lovelace quem criou o primeiro algoritmo resolvido pela máquina analítica, publicado como nota de rodapé de um artigo de Babbage. Nesse material, Ada descreveu a possibilidade de a máqui- na realizar cálculos complexos envolvendo letras, números e sím- bolos, além de instruções que permitiam repetição (looping). Além disso, constava nessas notas um algoritmo que permitia o cálculo para os números de Bernoulli. Foi por causa desse artigo que Babbage percebeu a geniali- dade da moça e aceitou trabalhar em conjunto com ela, o que se transformou em uma grande amizade. Na matéria “Ada Lovelace desafiou o machismo e se tornou a primeira programadora da história”, que retrata a história de Ada Lovelace sob o olhar da escritora Angela Saini, Simões (2021) relata que a “matemática estava muito à frente de seu tempo quan- do teve a genial ideia do que um algoritmo seria capaz de fazer”. Ada e Babbage trabalharam juntos ao longo de muitos anos. Nesse período, ela desenvolveu diversos algoritmos que permitiriam que a má- quina analítica computasse valores de funções matemáticas. Esses algo- ritmos foram posteriormente analisados por um outro matemático – que será apresentado mais à frente. Para conhecer um pouco mais da história e feitos de Babbage e Lovelace, sugerimos dois vídeos. O primeiro conta a vida de Lovelace. Já o segundo, traz a parceria entre Lovelace e Babbage na idealização e construção da máquina analítica. • Biografias 23 – Ada Lovelace, a primeira programadora. Disponível em: https://www. youtube.com/ watch?v=gcNKhlKW7uQ&ab_ channel=OMundoDaCi%C3 %AAncia. Acesso em: 31 maio 2021. • O primeiro Computador do Mundo – Charles Babbage & Ada Lovelace – Documentário. Disponível em: https:// www.youtube.com/ watch?v=35MwtZ5MKjM. Acesso em: 31 maio 2021. Vídeo https://www.youtube.com/watch?v=gcNKhlKW7uQ&ab_channel=OMundoDaCi%C3%AAncia https://www.youtube.com/watch?v=gcNKhlKW7uQ&ab_channel=OMundoDaCi%C3%AAncia https://www.youtube.com/watch?v=gcNKhlKW7uQ&ab_channel=OMundoDaCi%C3%AAncia https://www.youtube.com/watch?v=gcNKhlKW7uQ&ab_channel=OMundoDaCi%C3%AAncia https://www.youtube.com/watch?v=gcNKhlKW7uQ&ab_channel=OMundoDaCi%C3%AAncia https://www.youtube.com/watch?v=35MwtZ5MKjM https://www.youtube.com/watch?v=35MwtZ5MKjM https://www.youtube.com/watch?v=35MwtZ5MKjM 12 Matemática para Computação Mas o que é um algoritmo? Fazendo uma analogia simples, um algoritmo é como uma receita de bolo que mostra detalhadamente os métodos necessários para re- solver uma atividade. Na matemática, um algoritmo é fundamental para que consigamos resolver uma expressão. A seguir, veremos que na computação tam- bém é essencial. Exemρlo 1 Pense em um cálculo qualquer. Pode ser um cálculo simples, como (2 + 2) + 2 Um algoritmo para esse cálculo pode ser montado como a seguir: Início: Resolva primeiro os parênteses. Laço: Dentro dos parênteses procure operações de multiplicação e divisão. Se não houver, resolva as operações de adição e subtração. Com o resultado da soma, elimine os parênteses e some esse nú- mero com o restante das parcelas. Fim. O Exemplo 1 traz um algoritmo muito simples, escrito de maneira direta e, no momento, sem pensarmos como essa lista de regras seria realmente programada para que a máquina pudesse resolver. Porém, com esse exemplo, conseguimos visualizar a necessidade de regras claras sobre a maneira de resolução, pois sem elas o computador não irá operar corretamente. Essa forma de escrita que adotamos para re- presentar um algoritmo é conhecida como pseudocódigo ou portugol. Fica claro que sem os algoritmos e esse avanço trazido por Ada Lovelace é quase impossível pensarmos na ciência da computação e na matemática avançada da maneira que a vemos hoje. Por que estudar matemática? 13 1.1.2 Alan Turing Alan Mathison Turing nasceu em 23 de junho de 1912, na cidade de Paddington, na Inglaterra, e faleceu em 7 de junho de 1954, aos 41 anos, em Wilmslow, Inglaterra. Alan Turing é conhecido como o pai da ciência da computação e da inteligência artificial. Estudou na Universidade de Cambridge, onde obteve seu bacharelado em matemática e concluiu seu mestrado. Prosseguiu seus estudos, obtendo seu doutorado em matemática pela universidade de Princeton. Dentre os vários projetos que fizeram desse matemático o “cien- tista do século 20”, em pesquisa 1 realizada pela BBC no ano de 2019, ficando à frente de Albert Einstein e Marie Curie, está a chamada má- quina de Turing, também conhecido como máquina universal. A máquina de Turing é um modelo abstrato que permite mani- pular símbolosem uma fita de acordo com regras preestabelecidas, restringindo-se apenas aos aspectos lógicos do seu funcionamento, como a memória, os estados e as transições. Por meio dessa máqui- na, podemos modelar qualquer computador digital. Turing foi um dos responsáveis para que os Aliados – incluindo a Inglaterra – ganhassem uma importante vantagem em relação à Alemanha na Segunda Guerra Mundial. Sua máquina física Bombe, construída com os conceitos da máquina universal e tendo como referência os trabalhos de Lovelace e Babbage, dentre outros, per- mitiu que os Aliados quebrassem o código alemão Enigma em Blet- chley Park. Dessa forma, eles passaram a ter conhecimento das estratégias que seriam usadas e puderam se antecipar aos ataques, levando à vitória. Muitos outros nomes estão envolvidos na construção histórica da computação e na forma como trabalhamos com a matemática hoje. Dentre eles, citamos John Von Neumann (1903-1957) e Norbert Wiener (1894-1964). Contudo, percebemos que Ada Lovelace e Alan Turing, dois ma- temáticos, viram a matemática muito além do que cálculos reali- zados à mão, com abordagem abstrata e sem aplicação no mundo Alan Turing Bruno Barral/Wikimedia Commons Acesse na íntegra a pes- quisa Scientists of the 20th Century. Disponível em: https://www.bbc.co.uk/ programmes/p06y1tmk. Acesso em: 30 ago. 2021 1 Para saber um pouco mais sobre a vida e con- tribuição de Turing, suge- rimos a matéria 17 fatos e curiosidades sobre a vida do Alan Turing, publicada pela revista Galileu. Disponível em: https://revistagalileu. globo.com/Cultura/noticia/2018/06/ 17-fatos-e-curiosidades-sobre-vi- da-do-alan-turing.html. Acesso em: 31 maio 2021. Leitura O filme O jogo da imitação, de 2014 – indicado ao Oscar em duas categorias –, retrata vida e morte de Alan Turing, o processo de criação da máquina física Bombe e a guerra. Direção: Morten Tyldum. Reino Unido: Warner Bros, 2014. Filme https://revistagalileu.globo.com/Cultura/noticia/2018/06/17-fatos-e-curiosidades-sobre-vida-do-alan-turing.html https://revistagalileu.globo.com/Cultura/noticia/2018/06/17-fatos-e-curiosidades-sobre-vida-do-alan-turing.html https://revistagalileu.globo.com/Cultura/noticia/2018/06/17-fatos-e-curiosidades-sobre-vida-do-alan-turing.html https://revistagalileu.globo.com/Cultura/noticia/2018/06/17-fatos-e-curiosidades-sobre-vida-do-alan-turing.html 14 Matemática para Computação físico. Por meio de seus raciocínios analíticos, viram a possibilidade de resolver problemas de maneira mais rápida e otimizada e con- seguiram colocar em prática o que hoje chamamos de matemática computacional. 1.1.3 Por que estudar matemática computacional? A matemática computacional permite que trabalhemos com pro- blemas extremante complexos que não poderiam ser resolvidos por uma única pessoa e, muitas vezes, nem mesmo por uma grande equipe. Esse conceito pode parecer absurdo, mas é a realidade de nossos dias. Os computadores mudaram a vida em sociedade e por meio deles conseguimos trabalhar com operações complexas, com modelos cada vez mais elaborados que representam o mundo real, e analisar uma infinidade de dados que não conseguiríamos avaliar em gera- ções passadas. Além disso, entenda, sem uma quantidade de dados razoavel- mente grande – em torno de milhões – não teríamos os serviços cada vez mais personalizados, os sistemas otimizados e a precisão em diversos processos, que são exigências do mundo atual. Dessa forma, podemos entender a matemática computacional como uma nova ciência que une os conceitos da computação e da matemática e nos permite resolver problemas, por exemplo, repre- sentar o genoma humano, calcular a eficiência e ajuste de foguetes, dentre outros, que não seriam possíveis sem os computadores. Contudo, para que possamos levar para o computador a mate- mática por traz desses avanços, inicialmente precisamos compreen- der alguns conceitos, como: o que são dados quantitativos, como montar uma relação de recorrência ou, ainda, como escrever um algoritmo que resolva problemas envolvendo vetores, matrizes, sis- temas de equações, funções, dentre muitos outros. É desses questionamentos que nasce a ciência matemática com- putacional. Desse modo, precisamos entender a matemática e como Por que estudar matemática? 15 a máquina processa essa matemática? Com certeza! Além disso, pre- cisamos representar os problemas cotidianos em modelos matemá- ticos para que tenhamos essa associação. Desse modo, vamos trazer um pouco mais da matemática que precisamos compreender para que seja possível criar as oportunida- des de aplicação usando os computadores. Ev er et t C ol le ct io n/ Sh ut te rs to ck Figura 2 Mecanismo de Gottfried Leibniz 1.2 Idealização de um algoritmo numérico Vídeo Em 1671, o filósofo e mate- mático Gottfried Wilhelm Leibniz, um dos criadores – juntamente com Isaac Newton – do cálculo diferencial e integral, construiu um mecanismo (Figura 2) que permitia realizar multiplica- ções e divisões mediante adi- ções e subtrações sucessivas. Na época, a metodologia usada por Leibniz ocasionava muitos erros, sendo descartado seu uso. Entretanto, manteve-se a ideia principal, que permitia, por meio de operações simples, escrever outras operações. A primeira calculadora capaz de efetuar as quatro operações aritméticas básicas foi construí- da pelo francês Charles Xavier Thomas em 1820. Considerada a primei- ra calculadora possível de ser comercializada, a máquina de Thomas executava as multiplicações por meio de somas, como idealizado por Leibniz, e as divisões podiam ser executadas com auxílio do usuário. Contudo, nenhuma dessas máquinas era programável, ou seja, era possível entrar com valores numéricos, mas não era possível passar instruções. 16 Matemática para Computação Vimos que um algoritmo é constituído exatamente de ins- truções a serem realizadas e esse feito começa a ser possível apenas com a criação da máquina de Lovelace e Babbage e, posteriormente, com a máquina de Turing. Um algoritmo é uma etapa essencial para que uma construção matemática possa ser executada por um computador. Ao construirmos um algoritmo, não preci- samos pensar qual será a linguagem de programação utili- zada, mas sim como queremos que o cálculo seja realizado. Exemρlo 2 Acompanhe o algoritmo a seguir e observe o resultado obtido. Variáveis inteiras: a, soma Seja a=0 e Soma=0 Se Soma<6, faça: a=a+1 Soma=Soma+a Imprima Soma Vamos interpretar esse algoritmo: Variáveis inteiras: a, soma #Declaração de variáveis. Nesse pon- to apresentamos a que conjunto elas pertencem. Seja a=0 e Soma=0 #Valores iniciais das variáveis. Se Soma<6, faça: #Note que, nesse ponto temos um laço ou looping que será executado enquanto a condição “Soma<6” for válida. a=a+2 #Cada vez que entramos no laço, precisamos pegar o último valor de a e acrescentar 1, gerando um novo valor de a. Soma=Soma+a #Cada vez que entramos no laço, precisamos pegar o último valor de Soma e acrescentar a, gerando um novo valor para Soma. Imprima Soma #Quando não for mais possível realizar o laço, ou seja, quando “Soma ≥ 6”, imprime-se o último valor encontrado para a variável Soma. Charles Xavier Thomas Ba sti en M/ Wi kim edi a Co mmo ns Por que estudar matemática? 17 Quadro 1 Resumo do algoritmo a Soma Início 0 0 Laço a=0+1=1 Soma=0+1=1 Laço a=1+1=2 Soma=1+2=3 Laço a=2+1=3 Soma=3+3=6 Imprime Soma=6 Fonte: Elaborado pela autora. De acordo com Campos Filho (2007, p. 1), o cálculo numérico é uma metodologia para resolver problemas matemáticos por intermédio de um computador, sendo ampla- mente utilizado por engenheiros e cientistas. Uma solução via Cálculo numérico é sempre numérica, enquanto os métodos analíticos usualmente fornecem um resultado em termos de funções matemáticas. Para a construção de um algoritmo numérico, são necessárias as quatro operações aritméticas fundamentais e as operações lógicas que são: comparação, conjunção,disjunção e negação. A vantagem é que essas operações são exatamente as operações realizadas pelo processador de um computador. O processo se dá inicialmente pelo fechamento e abertura de cha- ves que permitem a passagem ou não de energia. Esse mecanismo é compilado em zeros e uns. Isto é, quando a energia passa, o compila- dor entende esse resultado como 1 (sim). Quando a energia não passa, esse resultado é igual a 0 (não). O processador permite que os cálculos binários sejam realizados e, a partir desse ponto, entra em jogo o sistema operacional que transfor- ma tudo o que você faz nessa linguagem binária, a qual é passada para o software, podendo, por sua vez, fazer o que você quer. Para auxiliar no entendimento desse processo binário, sugerimos o artigo Aritmética de números binários e suas relações com circuitos lógicos, dos auto- res Rafael Pinheiro Leite e Prof. Dr. Matheus da Silva Menezes. Acesso em: 31 maio 2021. https://repositorio.ufersa.edu.br/bitstream/prefix/5854/1/RafaelPL_ART..pdf Artigo 18 Matemática para Computação Para elaborar um algoritmo numérico, precisamos de algumas eta- pas anteriores. Exemplo: Queremos encontrar a divisão exata de a 2 �, com a > 0 usando apenas as quatro operações fundamentais. Definição do problema É a primeira etapa. Como o próprio nome sugere, é preciso compreender o que se deseja estruturar e as possibilidades de resposta. Modelagem A segunda etapa é por meio de uma formulação matemática. Transformamos o problema real em um problema matemático. Exemplo: Usando o exemplo anterior, escrevemos a {2x�|�x *� � � } Assim, modelamos a definição do problema colocando as características matemáticas necessárias para resolvê-lo. Nesse caso, identificamos que a precisa ser um número par para que tenhamos divisão exata. Solução numérica Nesta terceira etapa escolhemos o método numérico apropriado para resolver o modelo matemático. É nesse ponto que precisamos avaliar os métodos existentes e escolher aquele que resulte em menor erro numérico. A escrita do algoritmo entra nessa etapa e é idealizada aplicando as possibilidades do método escolhido. Kh vo st /S hu tte rs to ck ol eg ga nk o/ Sh ut te rs to ck TK 1 98 0/ Sh ut te rs to ck da vo od a/ Sh ut te rs to ck As duas últimas etapas não serão abordadas neste capítulo, visto que não é escopo desta obra trabalhar com as linguagens de progra- mação, entretanto, para que possamos registrar os passos seguintes à escrita do algoritmo, temos: Por que estudar matemática? 19 Codificação do algoritmo Processamento do programa A transformação do algoritmo para a linguagem de programação escolhida. Implementação do algoritmo na linguagem de programação escolhida. Nesse caso, o programa será escrito em um arquivo para ser executado. ST RI PB AL L/ Sh ut te rs to ck ST RI PB AL L/ Sh ut te rs to ck Kh vo st /S hu tte rs to ck Observe que a idealização de um algoritmo numérico passa pela etapa de modelagem do problema, que só é possível com o conheci- mento matemático sobre esse conteúdo. Já na etapa de solução numé- rica, além do entendimento dos métodos numéricos disponíveis para a resolução do modelo, é preciso analisar os possíveis erros obtidos com essa escolha. Essa etapa é otimizada quando entendemos os tipos de erros que podem ser gerados pelo computador. Muitos algoritmos usam as chamadas relações de recorrência para realizar seus cálculos e convergir para a resposta desejada. Vamos en- tender esse conceito na sequência. 1.3 Relações de recorrência Vídeo A base da maior parte dos algoritmos matemáticos vem do conceito de relação de recorrência. Uma relação de recorrência é uma técnica matemática que nos auxilia na definição de sequências, conjuntos, ope- rações ou algoritmos. Para que tenhamos uma fórmula de recorrência, 20 Matemática para Computação precisamos analisar as características do problema e escrever uma re- gra que o represente. Com o intermédio dessa regra, podemos calcular qualquer termo em função dos antecessores. Nesta seção, vamos trazer como objeto para entendermos as relações de recorrência a famosa fórmula de re- corrência de Fibonacci. Leonardo de Pisa, mais conhecido como Fibonacci, que significa fi- lho do Bonacci, descreveu sua sequência pela primeira vez em seu livro Liber Abaci, em 1202, a fim de modelar um problema relacionado com o crescimento de uma população de coelhos. Fibonacci desejava descrever a quantidade de casais em uma po- pulação de coelhos após n meses (Figura 3), partindo dos seguintes pressupostos (ZAHN, 2011): 1. nasce apenas um casal no primeiro mês; 2. casais amadurecem sexualmente após o segundo mês de vida; 3. assumimos que não há problemas genéticos no cruzamento consanguíneo; 4. todos os meses, cada casal dá à luz um novo casal; 5. os coelhos nunca morrem. Figura 3 Sequência de casais em uma população de coelhos M ag ic le af /S hu tte rs to ck Por que estudar matemática? 21 O que ele encontrou foi a fórmula de recorrência – uma função aritmética – da definição a seguir: Definição 1 Seja uma sequência de Fibonacci, formada por n termos e denotada por fn. Para calcularmos o n-ésimo termo dessa sequência fazemos: f n � � � � � � � � � � � � 0 0 1 1 11 2 , � � ,� � , � �� se n se n f f se nn n Com essa função podemos montar a sequência de Fibonacci e des- cobrir quantos coelhos foram gerados em cada mês. Vamos exemplifi- car essa definição. Exemρlo 3 Utilizando a fórmula de recorrência f f f n �n n � � � � � � � � � � � � 0 0 1 1 11 2 ,� � ,� �� � � ,�� � � se n se n se n Temos que: • f5 = f5–1 + f5–2 = f4 + f3 = 5; • f10 = f10–1 + f10–2 = f9 + f8 = 55. Os primeiros números da sequência de Fibonacci são: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89. Percebemos com esse exemplo a usabilidade das relações de re- corrência em processos matemáticos, principalmente nos processos que precisam ser transformados em algoritmos, para que possam ser programados. Para saber mais sobre as relações de recorrência e a sequência de Fibonacci, sugerimos dois vídeos do canal Programa de Inicia- ção Científica da OBMEP: • Aula 01 - Sequências definidas por recorrências – Disponível em: https://www.youtube.com/ watch?v=S9zDoNAr3d4. Acesso em: 31 maio 2021. • Indução Matemática - Aula 6 - Sequência de Fibonacci. Disponível em: https://www.youtube.com/ watch?v=QVlTuInyZKk. Acesso em: 31 maio 2021. Vídeo https://www.youtube.com/channel/UC5azyx8w7Y5qzASuxDSseOw https://www.youtube.com/channel/UC5azyx8w7Y5qzASuxDSseOw https://www.youtube.com/watch?v=S9zDoNAr3d4 https://www.youtube.com/watch?v=S9zDoNAr3d4 https://www.youtube.com/watch?v=QVlTuInyZKk https://www.youtube.com/watch?v=QVlTuInyZKk 22 Matemática para Computação 1.4 Conceito de função no aspecto computacionalVídeo Na matemática, uma função é uma “regra” que associa a cada ele- mento x ∈ X um único elemento y = f(x) ∈ Y (GUIDORIZZI, 2018). Temos que X e Y são conjuntos que podem conter elementos previamente de- finidos, por exemplo, números naturais, reais etc., ou outros tipos de elementos, como chapéus, aves, laços etc. Assim, desde que consigamos relacionar, por meio de uma regra, um elemento do conjunto X com um único elemento do conjunto Y, podemos dizer que estamos trabalhando com uma função. Na matemática, dizemos que essa regra é uma lei matemática. A notação usada para essa definição é dada por: f: X → Y Definição 2 No aspecto computacional, uma função pode ser escrita por meio da soma de um número finito de parcelas. Observe no exemplo a seguir como podemos representar uma fun- ção por meio de somas de infinitas parcelas. Esse é um processo mate- mático conhecido como séries de funções. Computacionalmente não é possível manusear somas infinitas, mas ao sintetizarmos a série, temos a representação da função com um erro aceitável. Exemρlo 4 Uma série geométrica da forma 1 + x2+ x4 + x6 + ... Representa uma função escrita como f x x � � � � 1 1 2 Até mesmo as funções trigonométricas podem ser escritas por meio de uma soma infinita de parcelas, como vemos no exemplo 5. Por que estudar matemática? 23 Exemρlo 5 senx x x x x ��� � � � �� � � �� � � � �� � � �� � � � �� � � �� �� 3 5 7 3 5 7! ! ! cos ! ! ! x x x x� � � � �� � � �� � � � �� � � �� � � � �� � � �� ��1 2 4 6 2 4 6 Essa forma de representarmos as funções é também chamada de série e comumente estudada em disciplinas de Cálculo Avançado. Essa é uma maneira de pensarmos em funções quando tratamos dos aspectos computacionais. Uma segunda abordagem do aspecto computacional das funções é a possibilidade de considerá-las como ferramentas de cálculo dentro de algoritmos. Por exemplo, na linguagem de programação PythonTM (Figura 4), uma função é uma sequência de comandos que executa al- guma tarefa. Essa sequência é geralmente nomeada, para que a função possa ser “chamada” sempre que necessária. Figura 4 Função cone em PythonTM #A is height B is radius def cone (a, b): formula = (3.14 * .33 *a)*(b * b) return formula Aa æ /W ik im ed ia C om m on s Consideremos o cálculo do volume de uma esfera, em que seu raio é conhecido. O exemplo a seguir mostra a estrutura lógica que permite realizar o cálculo desse volume, considerando r como uma variável que pode assumir qualquer valor real. Exemρlo 6 Crie uma função para o cálculo do volume de uma esfera de raio r. Solução r é real def esfera(r) Para conhecer um pouco mais das possibilidades de aplicação de séries numéricas usadas para representar funções, su- gerimos o vídeo Séries de Potências no Computador. Disponível em: http://eaulas.usp.br/ portal/video.action?idItem=7701. Acesso em: 31 maio. 2021. Vídeo Quer saber mais sobre funções em PythonTM? Sugerimos o material Funções. Disponível em: https://panda.ime. usp.br/pensepy/static/pensepy/ 05-Funcoes/funcoes.html. Acesso em: 31 maio. 2021. Saiba mais http://eaulas.usp.br/portal/video.action?idItem=7701 http://eaulas.usp.br/portal/video.action?idItem=7701 https://panda.ime.usp.br/pensepy/static/pensepy/05-Funcoes/funcoes.html https://panda.ime.usp.br/pensepy/static/pensepy/05-Funcoes/funcoes.html https://panda.ime.usp.br/pensepy/static/pensepy/05-Funcoes/funcoes.html 24 Matemática para Computação formula = 4/3 *(3,14)*r^3 return formula Agora podemos usar essa função. Assim, se escrevermos esfera(2), teremos como retorno o valor formula = 33 37 75 Entretanto, nos dois sentidos, podemos perceber o princípio fun- damental de uma função matemática, que é o de ser uma regra que vincula dois conjuntos de dados diferentes. 1.5 Diferenças entre problemas qualitativos e quantitativosVídeo Um problema é dito qualitativo quando os dados usados para re- solver o modelo são dados qualitativos, ou seja, são baseados em cará- ter subjetivo, em que são usadas narrativas escritas ou faladas. Uma pesquisa qualitativa pode reunir informações como o nome das pessoas que foram avaliadas em um determinado estudo, o estilo de vida desse grupo de pessoas, as preferências alimentares, hobbies, dentre outras informações que, em geral, são fornecidas por meio de narrativas, questionários abertos, entrevistas, observações etc., e que não são codificadas usando um sistema numérico. Uma pesquisa qualitativa pode ser dividida em pesquisa nominal ou ordinal. Como a própria nomenclatura sugere, uma pesquisa nominal é aquela em que temos como resposta à pesquisa “nomes”, sendo que não é possível ordenar tais respostas. Por exemplo, uma pesquisa que possui o campo “sexo”, terá como resposta “masculino” ou “feminino”. Esse tipo de resposta pode ser quantificado, contudo não conseguimos colocar ordem de importância para tal. Ainda no campo da pesquisa qualitativa, podemos ter dados ordi- nais. Nesse caso, é possível categorizar as variáveis em relação a de- terminado grau para cada categoria. Por exemplo, uma pesquisa que procura analisar o grau de instrução de seus participantes, pode conter a variável “nível de escolaridade”, como ensino fundamental e ensino médio. É possível construir uma classe para cada grau de escolaridade, e até quantificar os participantes em cada uma dessas, mas a variável continua tendo um teor puramente qualitativo. Por que estudar matemática? 25 O interesse quando modelamos um problema com o auxílio de pes- quisas quantitativas é identificar e compreender os fenômenos através de dados numéricos. Por exemplo, se desejamos saber a quantidade de pessoas que to- maram determinado remédio ou votaram em determinado candidato, precisaremos realizar pesquisas quantitativas. Podemos pensar na escolha de um método ou outro da seguinte forma: • Método qualitativo: geralmente é utilizado para categorizar uma determinada situação, classificar problemas e gerar hipóteses etc. • Método quantitativo: é utilizado, como o próprio nome remete, a quantificar objetos. Os métodos quantitativos são muito usa- dos na estatística. Em geral, adotam-se questionários que permi- tem a contagem das variáveis pesquisadas. O que caracteriza um método como quantitativo ou qualitativo são as variáveis que ele apresenta. Assim, chamamos de variáveis quanti- tativas as que possuem características que podem ser quantificadas, isto é, medidas em determinada escala quantitativa. Por esse motivo, são representadas numericamente e podem ser divididas em duas ca- tegorias: discretas ou contínuas. As variáveis discretas são representadas por valores (números) in- teiros. Alguns exemplos são: quantidade de filhos, de pessoas em de- terminado local e de produtos na geladeira. As variáveis contínuas recebem valores em uma escala contínua, em que podem estar presentes valores representados por frações e decimais (finitos ou infinitos). É comum a necessidade de instrumen- tos de medição para avaliar uma variável quantitativa contínua, como balanças, réguas, relógios e outros instrumentos de medição. Alguns exemplos desse tipo de variável são: idade, peso, altura etc. As variáveis qualitativas, ao contrário, não são representadas por valores que podem ser quantificados. Elas representam categorias, ou seja, algum tipo de classificação para pessoas, objetos ou situações, e podem estar subdivididas em duas categorias: nominais ou ordinais. As variáveis nominais não exigem ordenação, por exemplo: sexo, cor dos olhos, religião, profissão etc. Já as variáveis ordinais exigem ordenação dos dados coletados. São exemplos: classe social (A, B, C) e escolaridade (1º ano, 2º ano, 3º ano). Tanto um problema qualitativo como um problema quantitativo pode ser investigado para que seja “resolvido” com o auxílio de um al- goritmo executado computacionalmente. Mas é na pesquisa quantita- tiva que esses resultados têm ganhado destaque. A ciência de dados (Figura 5), considerada uma ciência estatística, teve seu início com a ideia de podermos resolver problemas matemáti- cos de maneira computacional. Figura 5 Áreas da ciência de dados CIÊNCIA DE DADOS Megadados Classificação de dados Análise de dados Estatística Solucionador Tomada de decisão Conhecimento aberto bu ffa lo bo y/ Sh ut te rs to ck . Ela pode ser definida como um conjunto de ferramentas e métodos que nos permitem analisar, visualizar e tomar decisões com base em dados (RAMOS, 2021). É aqui que a matemática e a computação, novamente, se encon- tram. A quantidade de dados gerados por ferramentas como Google, Netflix, Twitter, Uber, entre outras que usamos no nosso dia a dia, é imensa. Para coletar, organizar e aplicar em modelos que deem um retorno para essas empresas em forma de resultado financeiro, é ne- cessário que diversas áreas da matemática sejam envolvidas, dentre elas encontra-se a estatística, talvez a mais utilizada nesse sentido. Diana_Karch/Shutterstock Rede neural 2626 Matemática para ComputaçãoMatemática para Computação https://oestatistico.com.br/decisoes-big-data-feeling-better-data/https://oestatistico.com.br/decisoes-big-data-feeling-better-data/ Por que estudar matemática? 27 De acordo com Ramos (2021), “o chamado ‘cientista de dados’ é o profissional responsável por aplicar técnicas, modelos, tecnologias e processos para extrair informação relevante dos dados. Tudo isso com muita estatística e programação aplicada”. Dessa forma, pensar em algoritmos que possibilitam o uso des- ses dados é fundamental para o crescimento das empresas. Esses algoritmos poderão, por exemplo, estar vinculados ao marketing digi- tal, fazendo com que dados quantitativos e qualitativos gerem lucro. Nesse ponto, entram os chamados algoritmos de inteligência artifi- cial. Um dos quesitos necessários para esse tipo de algoritmo é que ele processe um grande volume de dados quantitativos ou qualitativos. A diferença desse tipo de algoritmo para os demais é a possibi- lidade de se aplicar um “fator de decisão”, ou seja, a existência de variáveis randômicas ou condicionadas, dentro de um domínio deter- minado, que permitirão que os resultados não sejam únicos, e sim ter uma gama de possibilidades definidas para o contexto aplicado. Nesse ponto, podemos ter algoritmos construídos com o uso de diferentes funções. É possível trabalhar em diferentes camadas e com funções matemáticas específicas para cada camada de dados. Perceba que, mesmo nesse quesito, o domínio sobre o algoritmo está na mão do programador. É ele quem determina o que serão es- ses “fatores de decisão” e como será seu comportamento matemático para que o cálculo se torne randomizado. A compreensão da mate- mática levará à obtenção dos resultados desejados. CONSIDERAÇÕES FINAIS Neste capítulo, trouxemos uma pequena parte do gigantesco mundo da matemática aplicada à computação, à qual nos referimos como mate- mática computacional. As possibilidades são enormes, a depender da área almejada. É possí- vel trabalhar desde processos de otimização de redes até a bela área da programação gráfica, passando pelo rico campo da inteligência artificial e da ciência de dados. Independentemente da área escolhida, a necessi- dade da compreensão da matemática que envolve todos esses cálculos é imprescindível para sua correta implementação. Desse modo, esperamos que você se sinta motivado a seguir nesse caminho que relaciona essas duas ciências: matemática e computação. 28 Matemática para Computação ATIVIDADES Sabendo que um algoritmo é compreendido como um processo que mostra detalhadamente os métodos necessários para a resolução de uma atividade, e que podemos pensar nessa estrutura em formato de pseudocódigo como estrutura inicial, descreva um pseudocódigo para o cálculo da expressão numérica 1 + 3(5 + 1). Atividade 1 Descreva o modelo matemático que pode ser utilizado para representar a definição do problema a , para a > 0, usando apenas as quatro operações aritméticas. Atividade 2 Uma pesquisa foi realizada coletando dados referentes à altura de alu- nos de uma sala de aula. Esse tipo de dado é qualitativo ou quantitativo? Justifique. Atividade 3 REFERÊNCIAS BIM, S. A. A vida de Ada Lovelace. Porto Alegre: Sociedade Brasileira de Computação, 2018. BROMLEY, A G. Charles Babbage’s Analytical Engine, 1838. Annals of the History of Computing, v. 4, n. 3, 1982. Disponível em: http://athena.union.edu/~hemmendd/Courses/ cs80/an-engine.pdf. Acesso em: 31 maio 2021. CAMPOS FILHO, F. F. Algoritmos numéricos: uma abordagem moderna de Cálculo Numérico. São Paulo: LTC, 2007. GUIDORIZZI, H. L. Um curso de cálculo. 6. ed. v. 1. Rio de Janeiro: LTC, 2018. KHOURY, J. Application to a probleme of Fibonacci. Disponível em: http://aix1.uottawa. ca/~jkhoury/fibonacci.htm. Acesso em: 31 maio 2021. RAMOS, R. Ciência de dados: uma breve história. O Estatístico. Disponível em: https:// oestatistico.com.br/ciencia-de-dados-uma-breve-historia/. Acesso em: 31 maio 2021. SIMÕES, I. Ada Lovelace desafiou o machismo e se tornou a primeira programadora da história. Darkside. Disponível em: https://darkside.blog.br/ada-lovelace-desafiou-o- machismo-e-se-tornou-a-primeira-programadora-da-historia/. Acesso em: 31 maio 2021. ZAHN, M. Sequência de Fibonacci e o Número de Ouro. Rio de Janeiro: Ciência Moderna, 2011. http://aix1.uottawa.ca/~jkhoury/fibonacci.htm http://aix1.uottawa.ca/~jkhoury/fibonacci.htm Noções sobre sistemas de numeração 29 2 Noções sobre sistemas de numeração Você já parou para pensar que o sistema de numeração que usamos na atualidade passou por diversas transformações ao longo da história para chegar ao que ele é hoje? Além disso, por muito tempo ele não foi único. Diferentes civilizações construíram seus próprios sistemas de numeração com os conhecimen- tos que tinham na época. E você sabia que esse sistema numérico que usamos, o indo-arábico, fortemente desenvolvido, embasado e com toda a estrutura matemática moderna construída sobre ele, é deixado de “lado” quando pensamos em cálculos realizados por um computador? Além do sistema de numeração adotado, quando o computador é usa- do ainda precisamos admitir propagações de erro. Sim, o computador comete muitos erros numéricos. Com o estudo deste capítulo, você será capaz de: • compreender os diferentes sistemas de numeração; • identificar erros numéricos e como interpretá-los; • caracterizar as diferentes representações numéricas computacionais; • compreender o conceito de erro numérico. Objetivos de aprendizagem 2.1 Sistemas de numeração Vídeo Um dos sistemas de numeração mais antigos foi encontrado, por meio de pesquisas arqueológicas, na Tchecoslováquia, Europa, em 1937, com data entre aproximadamente 35000 a.C. e 20000 a.C. Basicamente, 30 Matemática para Computação os pesquisadores encontraram um osso (tíbia) de lobo jovem com mar- cações unitárias feitas por meio de traços (cortes transversais), na forma: I II III IIII Ao todo eram 57 traços, sendo os primeiros 25 agrupados de 5 em 5 (ALMEIDA, 2011). Essa descoberta nos mostra a necessidade da contagem e possibili- ta discutir sobre os sistemas de numeração. O tipo de contagem observada nesse estudo é dita aditiva, em que, para se ter o próximo número, basta acrescentar uma marcação (|). Além disso, o sistema de numeração foi composto de apenas um sím- bolo, sendo chamado de sistema de numeração de base 1. A obra Através do espelho e o que Alice encontrou por lá, escrita em 1871 pelo matemático Lewis Carroll (1832-1898) e traduzida para mui- tos idiomas – inclusive o português –, traz um diálogo entre a rainha Branca e Alice, que demonstra a dificuldade que teríamos se o sistema de numeração de base 1 fosse adotado atualmente. Alice fala para a rainha que aulas servem para nos ensinar a fazer contas, e a rainha lhe pergunta: “e sabe Adição? Quanto é um mais um mais um mais um mais um mais um mais um mais um mais um mais um?”. Alice lhe res- ponde: “não sei. Perdi a conta” (CARROLL, 2013, p. 186). Na história da matemática identificamos diversas civilizações que adotaram sistemas ditos aditivos. Mas como exatamente (algebricamente) podemos definir um sistema aditivo? Vamos assumir que b é um número natural, tal que determinado sistema aditivo está escrito na base b. Assim, temos duas condições que precisam ser respeitadas: 1 O sistema deverá ter b símbolos para sua representação numérica, ou seja, teremos a1, a2, ..., ab símbolos para representar os números de um até b. Esses números deverão ser representados em ordem crescente. Caso tenha se interessado pelas obras de Carroll e queira saber um pouco mais sobre esse assunto, sugerimos o texto Lewis Carroll e a matemática do País das Maravilhas, publicado pela Sociedade Brasileira de Matemática. Disponível em: https://www. sbm.org.br/noticias/lewis-carroll- e-a-matematica-do-pais-das- maravilhas. Acesso em: 2 jun. 2021. Leitura https://www.sbm.org.br/noticias/lewis-carroll-e-a-matematica-do-pais-das-maravilhas https://www.sbm.org.br/noticias/lewis-carroll-e-a-matematica-do-pais-das-maravilhashttps://www.sbm.org.br/noticias/lewis-carroll-e-a-matematica-do-pais-das-maravilhas https://www.sbm.org.br/noticias/lewis-carroll-e-a-matematica-do-pais-das-maravilhas Noções sobre sistemas de numeração 31 2 Deve-se obedecer a regra do sucessor, que implica assumir que se um número termina em ai, com i ≠ b, então a representação de seu sucessor será obtida por meio da substituição de ai por ai+1. Caso a representação de um número termine em ab, seu sucessor será obtido acrescentando a1 à representação dada. Entre alguns dos sistemas aditivos mais importantes na história, en- contram-se o sistema hieroglífico (Figura 1), desenvolvido pelos egíp- cios por volta de 3400 a.C., e o sistema de numeração da antiga Grécia, desenvolvido por volta do século IV a.C. Figura 1 Sistema numeral egípcio Numerais egípcios Sistema numérico hieroglífico egípcio Sistema egípcio de numeração hierática Si dh e/ Sh ut te rs to ck No entanto, foi com o sistema chamado posicional que a matemáti- ca começou a se desenvolver com maior rapidez. 32 Matemática para Computação Não se tem consenso de qual foi a civilização que idealizou primeiro o chamado sistema de numeração posicional, em que se encontram o nosso sistema posicional de base decimal e o sistema binário computacional, mas o que se sabe é que, para esse tipo de construção, foi necessário o desenvolvimento lógico da ideia de agrupamentos entre os números. Nesse contexto histórico, identificou-se que os hindus praticaram o sistema posicional decimal e tiveram a preocupação de construir uma representação visual dele, que pudesse ser transferida de maneira escrita. Entretanto, foram os árabes que divulgaram esse sistema de numeração pelo ocidente, e por esse motivo o chamamos de sistema indo-arábico. Figura 2 Evolução do sistema posicional decimal Hindu – 300 a.C. Hindu – 500 d.C. Árabe – 900 d.C. Árabe – (Espanha) 1000 d.C. Italiano – 1400 d.C. Hoje Fonte: Elaborada pela autora. Um sistema de numeração posicional é aquele em que a posição na qual o algarismo se encontra modifica o seu valor, ou seja, no caso do sistema posicional de base decimal (o sistema que usamos), se o algarismo 1 estiver na posição (casa) da unidade, ele vale 1 unidade. Se o mesmo algarismo estiver na posição da dezena (casa da dezena), ele vale 10 unidades. Se estiver na posição da centena, vale 100 unidades, e assim sucessivamente. Usando o sistema numérico posicional decimal, a Tabela 1 apre- senta alguns exemplos com diferentes posicionamentos para o al- garismo 1. Noções sobre sistemas de numeração 33 Tabela 1 Posição do algarismo 1 em relação ao valor numérico obtido Classes Milhões Milhares Unidades simples Ordens c d u c d u c d u 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 Fonte: Elaborada pela autora. Um sistema de numeração posicional pode ser definido de maneira geral (algébrica), assim como fizemos para os sistemas posicionais. Nesse contexto, usaremos b ∈ ℕ como uma base qualquer. Assim, para construir um sistema posicional de base b, precisamos garantir duas con- dições. Por isso, considere b ≠ 1. Inicialmente, precisamos determinar b símbolos, sendo um desses destinado a representar a casa vazia (zero) e os demais destinados a representar os números de 1 a (b – 1). 1 Se o número a ser representado tem como unidade um dos algarismos que representam 0, 1, ..., (b – 2), ele terá um sucessor substituindo-se esse algarismo por seu sucessor, apresentado na ordem crescente, que será (b – 1). 2 Se o número a ser representado tem como unidade o algarismo que representa (b – 1), ele já é o último algarismo dessa base. Nesse caso a representação do sucessor será obtida substituindo-se esse algarismo por zero e, em seguida, aplicando-se recorrentemente os itens 1 e 2 dessa regra à casa seguinte. 3 Se a casa seguinte for vazia, considera-se como se ela tivesse o valor zero. Atualmente, o sistema de numeração posicional de base dez (siste- ma indo-arábico), em que a posição do algarismo indica a potência de 10 que o dígito representa, é usado em todo o mundo, sendo utilizado de maneira tão intuitiva, como uma criança pequena que usa os dedos para contar, que é difícil imaginar qualquer tipo de construção numéri- ca sem essa formatação. 34 Matemática para Computação Observe o exemplo de como decompomos um número no sistema posicional decimal por meio da representação geral enunciada. Exemρlo 1 x = (1957)10 = 1 · 10 3 + 9 · 10 2 + 5 · 101 + 7 · 100 Note que, com esse formato, fica evidente o uso da chamada base decimal. Essa formatação será adotada para a escrita das próximas ba- ses que estudaremos nesta obra. Queremos conceituar e identificar as características não só para o sistema posicional decimal, mas para outros sistemas posicionais que são usados na matemática e na computação, permitindo, assim, uma visão do cálculo numérico envolvido nesse processo. Definição 1 Dados um número natural com b > 1 e o conjunto de símbolos {±, 0, 1, 2, ..., b – 1}, a sequência de símbolos (dndn–1 ... d1d0, d-1d-2 ...)b representa o número positivo dn · b n + dn–1 · b n–1 + ... + d0 · b 0 + d–1 · b –1 + d–2 · b –2 + … Para representar números negativos, usamos o símbolo – à esquer- da do numeral, conforme exemplificamos a seguir. Exemρlo 2 x = (1.957,897)10 x = 1 · 103 + 9 · 102 + 5 · 101 + 7 · 100 + 8 · 10–1 + 9 · 10–2 + 7 · 10–3 x = 1.000 + 900 + 50 + 7 + 0,8 + 0,09 + 0,007 Portanto, percebemos que, além da escolha do sistema de numera- ção (aditivo ou posicional), há muitas representações distintas em rela- ção à quantidade de algarismos envolvida em cada um desses modelos (bases adotadas). Noções sobre sistemas de numeração 35 Na próxima seção, focamos nos sistemas posicionais mais utilizados pela matemática moderna e pela matemática computacional. 2.2 Representação numérica Vídeo Entender a representação numérica do sistema escolhido não só possibilita sua compreensão, mas viabiliza realizar operações com o tipo de numeração escolhido, além de permitir verificar possíveis erros cometidos nos cálculos. Como nosso foco é trabalhar com a matemática para a computa- ção, dedicaremos esta seção à representação numérica implícita nas máquinas digitais eletrônicas, ou seja, nos computadores. Assim, o primeiro sistema que vamos discutir é o chamado sistema de numeração posicional de base dois ou base binária. 2.2.1 Sistema binário Quando pensamos em um sistema de numeração que permita realizar operações no computador (chamamos de computador as má- quinas digitais eletrônicas), a base utilizada é a base dois. Seu uso está diretamente vinculado ao desenvolvimento das máquinas digitais. Durante muitos séculos se creditou a Gottfried Wilhelm Leibniz (1646-1716) a idealização da base binária. Para saber mais sobre Leibniz e a relação desse matemático com a base da computação, sugerimos a leitura de Leibniz e nosso mundo digital, de Gilberto Garbi, publicado pela Revista do Professor de Matemática (RPM). Acesso em: 2 jun. 2021. https://www.rpm.org.br/cdrpm/84/1.html Artigo Contudo, pesquisas recentes demonstram que em uma pequena ilha da Polinésia, séculos an- tes da idealização de Leibniz, o povoado de Mangareva já utilizava a base binária para rea- lizar cálculos que permitiam a comercialização de seus produtos. Gottfried Wilhelm Leibniz Nicku/Shutterstock 36 Matemática para Computação Ao analisar a pesquisa dos cientistas noruegueses Andrea Bender e Sieghard Beller, do departamento de ciência psicossocial da Universidade de Bergen, na Noruega, Javier Sampedro (2013) descreve que os pesquisadores mostram agora como os habitantes da Mangareva não só inven- taram o sistema para contar peixes, frutas, cocos, polvos e outros bens de diferente valor em suas transações comerciais, como tam- bém que isso conduziu a uma aritmética binária que teria mere- cido a aprovação do Leibniz por sua simplicidade e naturalidade. Dos fatos históricos, sabemos que a base binária foi deixa-da de lado até mesmo por Leibniz, e apenas séculos após sua morte, em 1841, foi redescoberta pelo matemático George Boole (1815-1864), o qual desenvolveu a chamada álgebra booleana, que permitiu o desenvolvimento do computador digital eletrônico, imprescindível para o desenvolvimento em praticamente todas as áreas do conhecimento na atualidade. O computador lida com grandezas representadas como se- quências de bits (base 2). Quando precisamos transcrever um método matemático para um mé- todo numérico, ou seja, para a matemática computacional, precisamos, em primeiro lugar, compreender como um computador manipula as in- formações – no nosso caso, as informações são numéricas e simbólicas. Toda informação manipulada por um computador é representada como uma sequência de bits (binary digits). Ao agrupar 8 bits, temos 1 byte; quando agrupados (Figura 3), os bytes darão origem aos kilobytes, megabytes, gigabytes, terabytes etc. – termos comumente usados na computação e no nosso dia a dia. Figura 3 Sequência de bits Ra hi m ov E m in /S hu tte rs to ck Medidas de informação eletrônica Célula de memória de 8 bits 0 1 0 1 1 0 1 0 1 byte = 8 bit 1 KB = 8.192 bit 1 KB = 1.024 byte 1 MB = 1.024 KB 1 GB = 1.024 MB 1 TB = 1.024 GB KB – kilobyte MB – megabyte GB – gigabyte TB – terabyte Sugerimos a leitura na íntegra do texto Um sistema binário inventado na Polinésia séculos antes de Leibniz, do autor Javier Sampedro. Disponível em: https://brasil. elpais.com/brasil/2013/12/16/ sociedad/1387215405_275511. html. Acesso em: 2 jun. 2021. Leitura George Boole Wd wd /W ikim edi a C omm ons https://brasil.elpais.com/brasil/2013/12/16/sociedad/1387215405_275511.html https://brasil.elpais.com/brasil/2013/12/16/sociedad/1387215405_275511.html https://brasil.elpais.com/brasil/2013/12/16/sociedad/1387215405_275511.html https://brasil.elpais.com/brasil/2013/12/16/sociedad/1387215405_275511.html Noções sobre sistemas de numeração 37 Um bit aceita duas respostas possíveis: • 0 – não, falso, desligado; • 1 – sim, verdadeiro, ligado. Na área eletrônica, interpreta-se isso como passagem de ener- gia (sim) ou sem passagem de energia (não). Essa leitura do código binário é feita milhares de vezes por segundo. Esse tipo de representação, também chamado de representação binária, matematicamente pode ser traduzido como um sistema de numeração na base dois. Exemρlo 3 Assim, para a codificação de um número natural entre 0 e 255, por exemplo, seriam suficientes 8 bits, pois 28 = 256. Desse modo, para representá-los, restaria apenas atribuir valores 0 ou 1. O número natural 255 será representado em uma sequência de bits (sequência binária) por 11111111. Mais adiante explicaremos os processos de conversão. Como demonstramos, o sistema de numeração na base dois, também chamado de binário na área da computação, tem seus al- garismos reconhecidos e representados por meio dos bits (binary digits). Já identificamos que um bit pode assumir dois valores dis- tintos: 0 ou 1. Embasados nos conhecimentos adquiridos até o momento so- bre base binária, começamos a trabalhar com as mudanças de base. Com essa finalidade, o exemplo a seguir apresenta uma mudan- ça da base binária para a base decimal, tendo como ideia principal o tipo de conversão adotada pelo computador. fli gh t o f i m ag in at io n/ Sh ut te rs to ck Representação do código binário pelos botões com símbolos I (ligado) e O (desligado). Figura 4 0 ou 1 Para conhecer mais sobre a relação entre bits e bytes e a sucessão de agrupamentos, sugerimos a leitura de Qual a diferen- ça entre Kilobyte, Megabyte, Gigabyte e Terabyte?, pu- blicado no site da Copel Telecom. Disponível em: https://www. copeltelecom.com/site/blog/ kilobyte-megabyte-gigabyte- terabyte/. Acesso em: 2 jun. 2021. Leitura https://www.copeltelecom.com/site/blog/kilobyte-megabyte-gigabyte-terabyte/ https://www.copeltelecom.com/site/blog/kilobyte-megabyte-gigabyte-terabyte/ https://www.copeltelecom.com/site/blog/kilobyte-megabyte-gigabyte-terabyte/ https://www.copeltelecom.com/site/blog/kilobyte-megabyte-gigabyte-terabyte/ 38 Matemática para Computação Exemρlo 4 Seja x = 1001,101, então 1 · 23 + 0 · 22 + 0 · 21 + 1 · 20 + 1 · 2–1 + 0 · 2–2 + 1 · 2–3 = 8 + 0 + 0 + 1 + 0,5 + 0 + 0,125 = 9,625 Portanto, (1001,101)2 = (9,625)10. Note que no exemplo utilizado respeitamos a posição de cada um dos elementos e fizemos a conversão, em primeiro plano, assumindo o valor de cada posição e, na sequência, somando esses resultados. Esse é o processo que será adotado para as bases que veremos na sequência. 2.2.2 Sistema quaternário No sistema quaternário a base b é igual a 4 e, portanto, temos o conjunto de algarismos {0, 1, 2, 3}. Exemρlo 5 Seja x = (301,2)4, então 3 · 42 + 0 · 41 + 1 · 40 + 2 · 4–1 = 48 + 0 + 1 + 0,5 = 49,5 Portanto, (301,2)4 = (49,5)10. Mais adiante veremos como converter uma base decimal para uma base qualquer. Na sequência, apresentamos a base hexadecimal, ou seja, uma base formada por 16 algarismos. 2.2.3 Sistema hexadecimal O estudo do sistema hexadecimal auxilia no processo de represen- tação de sequências maiores de bits, por exemplo, com 16 ou 32 bits. Se b > 10, usamos as letras A, B, C, ... para denotar A = 10, B = 11, C = 12, ... Para ficar claro esse sistema, vamos exemplificar. Noções sobre sistemas de numeração 39 Exemρlo 6 Se temos b = 16, ou seja, o conjunto de algarismos {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}, e queremos converter o número x = (E2AC)16 para a base decimal, fazemos: (E2AC)16 = 14 · 16 3 + 2 ·162 + 10 ·161 + 12 · 160 (E2AC)16 = 57.344 + 512 + 160 + 12 = 58.028 A base hexadecimal também é amplamente usada na computação. Você já ouviu falar do tripleto hexadecimal, também chamado de web color (Figura 5)? O tripleto hexadecimal recebe esse nome porque é uma combina- ção de 3 bytes, pois cada cor formada possui três duplas escritas em formato hexadecimal. Cada dupla representa uma cor, sendo elas: ver- melho, verde e azul (RGB). A variação da combinação hexadecimal no tripleto dará origem às demais cores. Figura 5 Web color R. A . N on en m ac he r/ W ik im ed ia C om m on s 40 Matemática para Computação Exemρlo 7 A cor azul-marinho é escrita como 12 0A 8F no sistema tripleto hexadecimal. Portanto, cada dupla terá 16 possibilidades para a primeira posição e mais 16 para a segunda, formando um byte de 256 possibilidades. Como temos três duplas, as possibilidades de combinação serão 256 · 256 · 256 = 16.777.216. Essa estrutura de cores é usada para documentos HTML, CSS, entre outros. É possível observar os códigos hexadecimais de uma quantidade considerável de cores e a conversão para outros sistemas de cores que podem ser adotados computacionalmente. A seguir, veremos o processo da transformação inversa, ou seja, co- nhecendo um número na base 10, converteremos ele para a base b desejada. 2.2.4 Processo inverso Nesta seção trabalharemos com a conversão de números na base decimal (x)10, os quais serão convertidos para uma base b qualquer. Ou seja, queremos trabalhar com a seguinte representação algébrica: (x)10 = (dndn–1 ... d0, d–1 ...)b (x)10 = dn · b n + dn–1 · b n–1 + … + d0 · b 0 + d–1 · b –1 + … Inicialmente, para conseguirmos realizar a conversão, separamos a parte inteira de (x)10 da sua parte fracionária (também chamada de mantissa), obtendo (x)10 = x i + xf. Assim, temos xi = dn · b n + dn–1 · b n–1 + … + d0 · b 0 x d b d b f � � ��� �1 1 2 2 Uma tabela bem extensa de combinações de cores pode ser encontrada no site Nas artes gráficas. Disponível em: http:// nasartesgraficas.blogspot. com/2014/08/lista-de-cores.html. Acesso em: 2 jun. 2021. Site http://nasartesgraficas.blogspot.com/2014/08/lista-de-cores.html http://nasartesgraficas.blogspot.com/2014/08/lista-de-cores.html http://nasartesgraficas.blogspot.com/2014/08/lista-de-cores.html Noções sobre sistemas de numeração 41 Portanto,precisamos determinar os valores para o conjunto {dn, dn–1, ...}, que é composto tanto de elementos da parte inteira como de elementos da parte fracionária. • Parte inteira (xi = dn · b n + dn–1· b n–1 + … + d0 · b 0) ÷ (b) = x b d b d b d d b i n n n n� � � � ��� �� � �1 1 2 1 0 Observe que d0 é o resto da divisão de x i por b, pois d1 + d2 ∙ b1 + ... + dn–1 · b n–2 + dn ∙ bn–1 é inteiro e d b 0 é uma fração com d0 < b. Da mesma forma, o resto da divisão de d1 + d2 ∙ b1 + ... + dn–1 · bn–2 + dn ∙ bn–1 por b é d1. Ou seja, repetindo esse processo encontramos os algarismos d0, d1, d2, ..., dn. Para a análise da parte inteira, temos uma ferramenta extremamen- te simples que pode ser usada: a divisão. Por meio de sucessivas divisões, podemos rapidamente converter um número da base decimal para a base binária. Exemρlo 8 Para a conversão de (3)10 para a base binária, fazemos: 3 ÷ 2 = 1 → Resto 1 1 ÷ 2 = 0 → Resto 1 O resultado será obtido, justamente, por meio dos restos. Portanto, (3)10 = (11)2. Também podemos converter um número na base 10 para a base binária por meio das divisões sucessivas, como é feito no exemplo a seguir. 42 Matemática para Computação Exemρlo 9 A conversão do número (142)10 para a base binária poderia ser re- solvida assim: (142)10 = (10001110)2 142 2 71 2 35 2 17 2 8 2 4 2 2 2 1 2 0 0 0 0 0 1 1 1 1 Por fim, um exemplo da conversão de bases de um número decimal. Exemρlo 10 Vamos converter o número 3,625 para a base binária (b = 2). Pri- meiramente, decompomos 3,625 na soma de suas partes inteira e fracionária. x = 3 + 0,625 Logo, xi = 3 e xf = 0,625. Nesse exemplo, resolveremos a parte inteira dessa conversão. Assim, precisamos fazer sucessivas divisões por b = 2. Então: xi = 3 = 1 · 2 + 1 = 1 · 21 + 1 · 20 Portanto, xi = 1 · 21 + 1 · 20 = (11)2. Para a parte fracionária do número, temos o seguinte: • Parte fracionária x d b d b b b x d d b f f� � �� � � � � � � � � � � � � � ��� � � �11 22 1 2 Noções sobre sistemas de numeração 43 Nesse produto, note que a parte inteira é d–1 e a parte fracionária é d b �� ��2 ; ao multiplicarmos novamente por b, temos d–2. Para encon- trar os algarismos restantes, repetimos esse processo. Exemρlo 11 Continuando o Exemplo 10, agora precisamos fazer sucessivas multiplicações por b = 2, para obtermos a parte fracionária do nú- mero 3,625. xf = 0,625 2 · xf = 1,25 · 2–1 = 1 · 2–1 + 0,25 · 2–1 = 1 · 2–1 + (0,5 · 2–1) · 2–1 = 1 · 2–1 + 0,5 · 2–2 = 1 · 2–1 + (1 · 2–1) · 2–2 = 1 · 2–1 + 1 · 2–3 Portanto, xf = 1 · 2–1 + 0 · 2–2 + 1 · 2–3 = (101)2. Logo, (3,625)10 = (11,101)2. Outras ferramentas computacionais podem ser usadas – entre elas, encontram-se algumas linguagens de programação, como Sclilab e PythonTM. Aqui, relembramos que o processo aplicado pelo computador é o de converter de binário para decimal, mas as conversões são impor- tantes para garantir a veracidade dos nossos cálculos e a viabilidade de possíveis aplicações. 2.3 Representação em ponto flutuante Vídeo Um número, na matemática, pode ser infinito, e isso é impossível de ser representado no computador, visto que este trabalha com um número de bits limitado e predefinido (WEBER, 2004). Pensando na estrutura numérica computacional, dizemos que há três formas possíveis de representação de um número no computador: I. Inteiro natural. II. Inteiro relativo. III. Generalização dos dois casos anteriores, ou seja, um número real. 44 Matemática para Computação É possível representar números inteiros, ou seja, considerar a parte negativa do conjunto, atribuindo um bit mais à esquerda, cha- mado de sinal ou bit forte. Por meio desse primeiro bit saberemos se o número é positivo ou negativo. Já no caso dos números reais, ou seja, considerando também núme- ros decimais, a Institute of Electrical and Electronic Engineers (IEEE) defi- ne uma fórmula para ser aplicada (padrão IEEE754). Essa representação (Quadro 1) é chamada de representação em ponto flutuante. Seja um com- putador de 32 bits, essa estrutura fica escrita da seguinte forma: (–1)S ∙ bE ∙ F Quadro 1 Organização do ponto flutuante S bit1� E F Fonte: Elaborado pela autora. Em que: • b é a base; • S = 0 (número positivo) ou S = 1 (número negativo); • E deve ser calculado por m ≤ E ≤ M, com m sendo o valor míni- mo que a máquina pode representar e M sendo o valor máximo (|m| ≈ M); • F, chamado de mantissa, conterá os bits situados após a vírgula. Acompanhe o exemplo a seguir para compreender melhor. Exemρlo 12 Considere uma máquina com registro de 32 bits e base b = 2. Pelo padrão IEEE754 (Quadro 2), 1 bit será usado para o sinal (S), 8 bits serão usados para o expoente (c7, ..., c0) e 23 bits serão usados para a man- tissa (d1, ..., d23). Quadro 2 Padrão IEEE754 S c7 c6 ... c0 d1 d2 ... d22 d23 Fonte: Elaborado pela autora. Se você se interessou por esse tema, sugerimos a leitura do material Padrão IEEE 754 para aritmética binária de ponto flutuante. Disponível em: https://www.lia.ufc. br/~valdisio/download/ieee.pdf. Acesso em: 2 jun. 2021. Leitura https://www.lia.ufc.br/~valdisio/download/ieee.pdf https://www.lia.ufc.br/~valdisio/download/ieee.pdf Noções sobre sistemas de numeração 45 Assumindo que E = c – BIAS, em que BIAS é o valor do deslocamento do expoente (polarização), temos: x = (–1)S ∙ 2c–BIAS F com c = (c7c6 ... c0)2 e F = (1,d1d2 ... d22d23) De acordo com Gilat e Subramaniam (2008, p. 23, grifos do original), “computadores armazenam números e realizam cálculos em precisão simples ou em precisão dupla. Na precisão simples, os números são armazenados em uma cadeia de 32 bits (4 bytes), e, na precisão dupla, em uma cadeia de 64 bits (8 bytes)”. Exemρlo 13 Queremos representar em notação ponto flutuante os números • x = (1)10 • y = (–11)10 • z = (231)10 assumindo precisão simples (32 bits) e base hexadecimal. No primeiro caso, x = (1)10, teremos a primeira casa composta do sinal, logo S = 0, pois 1 é positivo. Assim: 0 0 1 0 0 0 0 0 0 Agora, no segundo caso, y = (–11)10, como o valor é negativo, a pri- meira casa será representada por S = 1. Assim: 1 b 0 0 0 0 0 0 0 No último caso, ou seja, z = (231)10, teremos S = 0 e a representação: 0 e 7 0 0 0 0 0 0 Note que na representação em ponto flutuante dos três números não usamos as casas referentes a: d1 d2 ... d22 d23 Isso porque em nenhum deles há parte fracionária. 46 Matemática para Computação Note que aumentar o número de bits na mantissa melhora a preci- são. Já aumentar a quantidade de bits no expoente permite que tenha- mos um intervalo de números representáveis muito maior. Com isso, é possível perceber padrões muito bem definidos para a construção do cálculo numérico e da matemática computacional. 2.4 Erros numéricos Vídeo Quando falamos de erros, estamos tratando da diferença entre o valor real e o valor obtido. É comum que sejam necessárias diversas simplificações do pro- blema real para que se tenha um modelo matemático com solução possível. Observe a Figura 6 a seguir, que apresenta a comparação entre um modelo físico (geoide) e um modelo matemático (elipsoide) da super- fície da Terra. Figura 6 Comparação entre modelos Modelo físico – geoide jd rv _a rt/ Sh ut er st oc k Modelo matemático – elipsoide Al ex an de rZ am /S hu te rs to ck Assim sendo, o processo de propagação de erros começa quan- do transformamos um problema real em um modelo físico e este em um modelo matemático. Tal modelo matemático poderá ser resolvido de modo que tenhamos uma solução analítica ou uma solução numérica. Noções sobre sistemas de numeração 47 Ku bk o/ Sh ut te rs to ck Problema real Modelo físico Modelo matemático Solução analítica Solução numérica Implementação computacional Resultado numérico Note que ao desenvolvermos o modelo matemático, precisamos escolher entre a obtenção de uma solução analítica e uma solução numérica. Neste ponto, temos um grandequestionamento. Por que usar um método numérico? A resposta é mais simples do que imaginamos. Os modelos que possuem solução analítica precisam ser extremamente simplificados. Já os modelos que podem ser resolvidos numericamente podem con- 48 Matemática para Computação ter mais variáveis e equações e, assim, um requinte maior nas equa- ções que os contemplam. Como o modelo usado para a obtenção numérica é mais “refinado”, o erro inerente ao método e à máquina pode ser muito menor se compa- rado ao erro obtido com a solução analítica, que foi encontrada por meio de um modelo muito mais “grosseiro”. Com isso, concluímos que nem sempre usamos o mesmo modelo matemático para as duas abordagens. Em geral, modelos matemáticos computacionais podem abranger um número maior de situações quan- do comparados ao problema real. Por meio do arredondamento e do truncamento, que especificare- mos na sequência, conseguimos perceber a propagação de erros a que a resolução de um problema pode estar exposta. Como vimos, os números não são representados computacionalmen- te de maneira exata. Essa “perda” dependerá da capacidade da máquina. A precisão, denotada por p, de um computador é o número de dígi- tos significativos usados para representar um número. Os dígitos signi- ficativos são todos os dígitos certos adicionados ao primeiro algarismo duvidoso. Dessa forma, os números infinitos (ou mesmo muito grandes) aca- bam sendo arredondados ou truncados, ocasionando erros. Esses mesmos números, quando em operações, ocasionarão a chamada pro- pagação de erros. Além desses erros, ainda temos a chamada incerteza dos dados e os erros de modelagem matemática. Nesse caso, em vez de pensar na transformação de um número para sua forma finita, levamos em con- sideração a construção do modelo matemático e, com isso, a acurácia dos instrumentos de medição que estão envolvidos na construção desse modelo, além das ferramentas matemáticas disponíveis para solucionar o problema. Vamos entender qual tipo de ajuste é necessário quando arredon- damos ou truncamos um número e o que isso acarreta para o cálculo. 2.4.1 Erro de arredondamento O arredondamento de um número é feito analisando o primeiro al- garismo após o dígito duvidoso. acurácia: “[Física] Proxi- midade entre o resultado de um instrumento de medida e o verdadeiro valor do que foi medido” (DICIO, 2021). Glossário Noções sobre sistemas de numeração 49 Caso o dígito duvidoso seja maior do que 5, aumenta-se de uma unidade o algarismo duvidoso e desprezam-se os demais. Caso o dígito duvidoso seja menor do que 5, mantém-se o valor do algarismo duvidoso e desprezam-se os demais. Caso o dígito duvidoso seja igual a 5, há dois caminhos: • Se o algarismo duvidoso imediatamente anterior à parte despre- zada for um número ímpar, deve-se aumentá-lo em uma unidade. • Se o algarismo duvidoso imediatamente anterior à parte despre- zada for um número par, deve-se deixá-lo como está (inalterado). di fu gi c re at ive /S hu tte rs to ck Para compreender essas especificações sobre arredondamento, acompanhe o exemplo a seguir. Exemρlo 14 1 3 0 333 0 33� � �� � �, � , π = 3,1415926 ... ≈ 3,141693 1,55500... ≈ 1,56 0,805... ≈ 0,80 Adotamos o arredondamento numérico porque computacional- mente não é possível representar números infinitos, ou seja, esse tipo de ajuste é feito por causa das limitações existentes na representação numérica em máquinas digitais. Mas existem outros tipos de erros que podem se propagar quando transformamos um problema. 2.4.2 Erro de truncamento O chamado truncamento será o corte aplicado aos dígitos não sig- nificativos de um número infinito (ou muito grande), de acordo com a precisão possível da máquina. 50 Matemática para Computação O truncamento também ocorre quando se aplica um método numé- rico na solução de um problema e esse método leva a uma sucessão de termos infinitos. Computacionalmente, essa abordagem não é possível; nesses casos, trunca-se a série de termos em determinado ponto no qual o erro seja aceitável. Em geral, é necessário definir em cada problema o que é conside- rado um erro aceitável. Assim, o resultado encontrado, após o trunca- mento, será analisado perante a obtenção desse erro. Resumidamente, um erro de truncamento ocorre quando transfor- mamos uma representação de um processo infinito em uma represen- tação finita. É comum, por exemplo, truncarmos séries de funções, como no exemplo a seguir. Exemρlo 15 Seja a função sen x escrita por meio de uma série de potências na forma: sen x x x x x� � � � �� 3 5 7 3 5 7! ! ! Sabemos que o valor de sen �π 6 é igual a 1 2 . Contudo, se calcular- mos esse valor por meio de uma série de potências trigonométrica truncadas, teremos: sen � � � � � 6 6 6 3 2 1 6 5 4 3 2 1 6 7 6 5 3 5 7 � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �44 3 2 1� � � Nesse caso, sen � 6 0 49999999187� � � � � � � , . Note que para esse cálculo, além do erro de truncamento, ainda te- mos um erro de arredondamento. Portanto, começamos a perceber a propagação de erros intrínseca em diversos métodos computacionais. 2.4.3 Erro absoluto e erro relativo Com os ajustes numéricos necessários para a representação com- putacional (arredondamento, truncamento etc.), além dos ajustes nos Noções sobre sistemas de numeração 51 modelos e nas demais aproximações aplicadas, surge a questão refe- rente à quantificação dos erros envolvidos nesses processos. Para verificar se o resultado atingido foi bom, é necessário compará- -lo ao resultado exato. Nesse ponto, surgem algumas métricas que nos permitem quanti- ficar os erros. As medidas de erro mais utilizadas são o erro absoluto e o erro relativo. Definição 2 – erro absoluto Sejam x um número real e�x sua aproximação. O erro absoluto da aproximação �x é definido, de acordo com Justo et al. (2021), como: E x xA � � Apresentamos a seguir um exemplo que nos auxilia na compreen- são do cálculo para esse tipo de erro. Exemρlo 16 A área da circunferência é dada por A = πr². Se r = 3, então a área exata será dada por A = 9π. Mas o que ocorre se π for arredondado? Sejam π1 = 3,14 e π2 = 3,141593. Então, A1 = 9 · 3,14 = 28,26 e A2 = 9 · 3,141593 = 28,274337. Erro absoluto: E x xA � � → EA = |28,274337 – 28,26| = 0,014337. Em muitos casos, desejamos calcular uma taxa entre o erro e a solu- ção real. Nessa situação, precisamos do chamado erro relativo, definido a seguir. Definição 3 – erro relativo Sejam x um número real e�x sua aproximação. O erro relativo da aproximação �x é definido, de acordo com Justo et al. (2021), como: E x x x �xR � � �, 0 O erro relativo é adimensional e, muitas vezes, é expresso em porcentagens. 52 Matemática para Computação Exemρlo 17 Utilizando os mesmos dados do Exemplo 14, vamos calcular o erro relativo. Sejam π1 = 3,14 e π2 = 3,141593. Então, A1 = 9 · 3,14 = 28,26 e A2 = 9 · 3,141593 = 28,274337. Erro relativo: E x� �x xR � � . E � � � � %R � � � � � 28 274337 28 26 28 274337 0 0005070675927 100 0 050 , , , , , 77% Uma forma de minimizar o alastramento de erros em um modelo numérico é reduzir o número de operações. Exemρlo 18 Considere o polinômio dado por: pn(x) = anx n + an–1x n–1 + … + a1x 1 + a0 = ((…(anx + an–1)x + an–2)x + …a1)x + a0 Note que a primeira representação do polinômio contém mais ope- rações do que a segunda representação. Sendo assim, o erro geral no segundo caso será menor, pois serão necessários menos ajustes numéricos e, com isso, um menor alastra- mento de erros. Esse tipo de manipulação precisa ser trabalhado com suas especifi- cidades, dentro de cada método numérico e cada situação que permita a implementação computacional. CONSIDERAÇÕES FINAIS Neste capítulo percorremos trechos da história da matemática que permitiram o desenvolvimento da história da computação. Identificamos alguns matemáticos que estiveram diretamente relacionados com a construçãonão só das linguagens de programação, mas da própria má- quina digital eletrônica (computador moderno) e do modo como ela opera. • O relato de alguns acidentes atribuídos a erros de cálculo numérico pode ser encontrado na leitura de Some disasters attributable to bad numerical computing. Apesar de o texto estar em língua estrangeira, ele pode ser facilmente traduzido por meio de um tradutor on-line. Disponível em: http://www- users.math.umn.edu/~arnold// disasters/. Acesso em: 2 jun. 2021. • Além disso, indicamos também a leitura de Erros de cálculo na engenharia. Disponível em: https://www. aedb.br/seget/arquivos/ artigos18/23226187.pdf. Acesso em: 2 jun. 2021. Leitura http://www-users.math.umn.edu/~arnold//disasters/ http://www-users.math.umn.edu/~arnold//disasters/ http://www-users.math.umn.edu/~arnold//disasters/ https://www.aedb.br/seget/arquivos/artigos18/23226187.pdf https://www.aedb.br/seget/arquivos/artigos18/23226187.pdf https://www.aedb.br/seget/arquivos/artigos18/23226187.pdf Noções sobre sistemas de numeração 53 Percebemos a importância das estruturas lógicas-matemáticas en- volvidas no processo por trás da lógica computacional e, com isso, re- pensamos algumas das estruturas matemáticas clássicas que, quando convertidas para serem interpretadas pelo computador, ainda mantêm suas caraterísticas principais, ou seja, mantêm sua estrutura matemática. Com base em todos esses conceitos, reforçamos a importância do es- tudo da matemática para todos interessados pela área da computação, com todas as suas ramificações e possibilidades. ATIVIDADES Podemos considerar o sistema de numeração romano um sistema aditivo ou um sistema posicional? Explique. Atividade 1 É possível converter um número na base 10 para a base hexadecimal por meio de divisões sucessivas? Explique essa conversão e converta o número (9)10 para essa base. Atividade 2 Considere a escrita do número de Napier da forma e = 2,718... e e n n � � � � � �� � � 0 1 1 0 1 1 1 2 1 3 � ! ! ! ! ! No primeiro caso, devemos usar qual tipo de ajuste numérico para obter um número finito? E no segundo caso? Quais são os erros envolvidos em cada um dos casos? Atividade 3 REFERÊNCIAS ALMEIDA, M. C. Origens da matemática: a pré-história da matemática – o neolítico e o alvorecer da história. Curitiba: Progressiva, 2011. (v. 1) CARROLL, L. Aventuras de Alice no país das maravilhas & Através do espelho e o que Alice encontrou por lá. São Paulo: Zahar, 2013. DICIO. Dicionário Online de Português. 2021. Disponível em: https://www.dicio.com.br/. Acesso em: 2 jun. 2021. GILAT, A.; SUBRAMANIAM, V. Métodos numéricos para engenheiros e cientistas: uma introdução com aplicações usando o MATLAB. Porto Alegre: Bookman, 2008. JUSTO, D. A. R. et al. REAMAT: cálculo numérico. Porto Alegre: UFRGS. Disponível em: https:// www.ufrgs.br/reamat/CalculoNumerico/livro-sci/main.html. Acesso em: 2 jun. 2021. SAMPEDRO, J. Um sistema binário inventado na Polinésia séculos antes de Leibniz. El País, 16 dez. 2013. Disponível em: https://brasil.elpais.com/brasil/2013/12/16/ sociedad/1387215405_275511.html. Acesso em: 2 jun. 2021. WEBER, R. F. Fundamentos de arquitetura de computadores. v. 8. Porto Alegre: Bookman, 2004. https://www.ufrgs.br/reamat/CalculoNumerico/livro-sci/main.html https://www.ufrgs.br/reamat/CalculoNumerico/livro-sci/main.html https://brasil.elpais.com/brasil/2013/12/16/sociedad/1387215405_275511.html https://brasil.elpais.com/brasil/2013/12/16/sociedad/1387215405_275511.html 54 Matemática para Computação 3 Matrizes Quando falamos em matemática para computação, temos como objetivo possibilitar uma base para conceitos que serão usados não só como ferramenta para desenvolver e aprimorar o raciocínio lógico dentro da matemática e de outras disciplinas, mas também como ins- trumento essencial para a programação – seja esta como objeto de aprendizagem teórico ou mesmo como objeto aplicado. Você já se perguntou quanta matemática está por trás de um sim- ples software de reconhecimento de imagem? Ou como transformar um problema real em um problema computacional? É a matemática envolvida nessas situações que queremos apresentar. Assim, iniciamos com o conceito de matriz, possivelmente já visto por muitos de vocês no ensino médio, mas que será reforçado, nesse momento, para que possamos ampliar o nosso ferramental aplicado à computação. Dessa forma, este capítulo trará a estrutura das matrizes e as suas propriedades, pois queremos possibilitar o entendimento da relação desse conceito com estruturas vetoriais, listas, arrays, dentre outros, que são essenciais na maior parte das linguagens de programação. Na sequência, aprofundaremos a definição de operação matricial, abordando determinantes, matrizes inversas e fatoração de matrizes. Essa base auxiliará no entendimento de construções da lógica da pro- gramação e na aplicação dessa lógica voltada ao tratamento vetorial, ao processamento numérico e à modelagem computacional. A ideia é possibilitar um estudo crítico e de real aprendizado, direcionado para as necessidades da profissão e do mundo que nos cerca. Matrizes 55 Com o estudo deste capítulo, você será capaz de: • relacionar o conceito de vetor e matriz; • pensar a definição de multiplicação matricial de modo computacional; • compreender o conceito de base de espaços formados por vetores, para a agilidade dos resultados computacionais; • entender e aplicar o processo de fatoração matricial, conhe- cido por método de Gauss; • aplicar o conceito de algoritmo para resolver os processos de fatoração e decomposição matriciais; • interpretar a inversa de uma matriz por meio de processos de decomposição matricial. Objetivos de aprendizagem 3.1 Vetores de uma matriz Vídeo Você conhece as regras do jogo de xadrez? Antes de entender qual- quer regra que envolva esse tipo de jogo, precisamos conhecer o tabu- leiro, pois toda e qualquer regra estará vinculada à posição em que as peças se encontram. Assim, o tabuleiro de xadrez é formado por linhas, representadas por números, e colunas, retratadas por letras, conforme podemos observar na Figura 1. Figura 1 Linhas e colunas no xadrez Va pa rt/ Sh ut te rs to ck 56 Matemática para Computação Assim, quando o jogador pensa na movimentação que fará com sua peça, ele identifica a linha e a coluna para onde fará o movimento. Por exemplo, o peão branco na casa 2D pode se movimentar para a 4D. Outro peão branco, localizado na casa 2C, pode avançar para a 4C. Na Figura 2, temos o peão preto, que foi movido para a casa 5D. Dimitrios Karamitros/Shutterstock Figura 2 Movimentação no tabuleiro de xadrez Note que compreender a movimentação por meio de linhas e colunas 1 facilita muito a escrita de jogadas. Se isso não fosse normali- zado dessa forma, seria bem difícil explicar diferentes jogadas e movi- mentações para outros jogadores por intermédio de obras literárias e artigos técnicos. Partindo dessa ideia, definimos matematicamente o conceito de matriz. Definição 1 Chama-se matriz de ordem m por n a um quadro de m ⨯ n elementos dispostos em m linhas e n colunas da seguinte forma (LEON, 2019): A a a a a a a a a a am n n n m m mn ij m� � �� � � � � � � � � � � � � 11 12 1 21 22 2 1 2 � � � � � � [ ] ��n Se pensarmos em matriz como uma forma de organizar coisas em posições específicas, é possível perceber que os elementos dessa ma- triz podem ser qualquer objeto. Contudo, matematicamente, entende- mos os elementos de uma matriz como números (reais ou complexos), funções ou, ainda, outras matrizes. Ficou curioso com as movimentações possíveis do jogo de xadrez? Suge- rimos a leitura de duas obras que podem ajudá-lo nessa área e, como consequência, no entendi- mento das matrizes: SUMMERSCALE, C. Xadrez: guia passo a passo totalmente ilustrado. São Paulo: Zastras, 2008. NIMZOWITSCH, A. Meu sistema: o primeiro livro de ensino de xadrez. São Paulo: Solis, 2007. LeituraEstamos usando a nomenclatura usual para matrizes (linha e coluna), mas, no xadrez, o padrão é nomear primeiro a colu- na e depois a linha. 1 https://www.amazon.com.br/Xadrez-Guia-Passo-Totalmente-Ilustrado/dp/8521313993/ref=sr_1_2?__mk_pt_BR=%C3%85M%C3%85%C5%BD%C3%95%C3%91&dchild=1&keywords=xadrez+para+ilustrado&qid=1623522307&s=books&sr=1-2 https://www.amazon.com.br/Xadrez-Guia-Passo-Totalmente-Ilustrado/dp/8521313993/ref=sr_1_2?__mk_pt_BR=%C3%85M%C3%85%C5%BD%C3%95%C3%91&dchild=1&keywords=xadrez+para+ilustrado&qid=1623522307&s=books&sr=1-2 Matrizes 57 A nomenclatura usual para uma matriz é dada por: Ol lie T he D es ig ne r/ Sh ut te rs to ck Letras maiúsculas para simbolizar matrizes. Letras minúsculas para denotar seus elementos. A posição de cada elemento é apresentada por meio de subíndices, sendo que usamos i para a posição do elemento em relação à linha e j para a posição do elemento em relação à coluna aij. Para indicar a ordem de uma matriz A (isto é, o número de linhas e colunas), escreve-se Am⨯n, sendo que m representa o número de linhas, e n o de colunas. Cada elemento da matriz A tem dois índices: aij, sendo que o primei- ro índice representa a linha a que esse elemento pertence, e o segundo a coluna. Dessa forma, [aij], com i variando de 1 a m, e j de 1 a n, repre- sentamos abreviadamente a matriz A de ordem m por n. Ol lie T he D es ig ne r/ Sh ut te rs to ck Duas matrizes A = [aij] e B = [bij] de ordem m por n são iguais (equivalentes) se, e somente se, aij = bij. A matriz de ordem n por 1 é uma matriz coluna: A a a a an n ij n� �� � � � � � � � � � � � � � � �1 11 21 1 1 [ ] A matriz de ordem 1 por n é uma matriz linha: A a a a an n ij n1 11 12 1 1� �� ��� �� � [ ] 58 Matemática para Computação Cada linha (ou coluna) representa um vetor. Assim, se a matriz é de ordem m por n, teremos vetores m, vetores linha ou n vetores coluna. Logo, o que determina se olharemos para as linhas ou para as colu- nas como vetores é a aplicação relacionada a essa matriz. De acordo com Feofiloff (2018): um vetor, ou arranjo (= array), é uma estrutura de dados que armazena uma sequência de objetos, todos do mesmo tipo, em posições consecutivas da memória RAM (= random access memory) do computador. Essa estrutura permite acesso aleató- rio: qualquer elemento do vetor pode ser alcançado diretamen- te, sem passar pelos elementos anteriores (o décimo elemento, por exemplo, pode ser alcançado sem que seja necessário passar antes pelo primeiro, segundo, etc., nonos elementos). Note que Feofiloff (2018) usa termos específicos da computação, mas que são, simplesmente, conceitos matemáticos que já conhece- mos: vetores e matrizes. Um array pode ser unidimensional ou multidimensional. Quando o array é unidimensional, temos o vetor, que é capaz de armazenar mui- tas variáveis do mesmo tipo. Uma coleção de arrays, ou seja, um array multidimensional, é entendida como uma matriz; também pode ser compreendida como um vetor de vetores. Cada elemento da matriz é acessado pelos seus índices, ou seja, i e j, que determinam a posição desse elemento. A proposta do nosso material não é a de simplesmente revisar o conceito de matriz, mas a de trazer uma nova abordagem para este, pensando na sua aplicação na computação. Para isso, vamos focar as maneiras de aplicarmos as matrizes e os seus vetores, tendo como objetivo as operações realizadas computacionalmente. É nesse contexto que entramos na próxima seção, na qual aborda- remos as operações matriciais e os algoritmos. 3.2 Análise do algoritmo padrão para multiplicação de matrizes Vídeo Talvez você já tenha pensado no processo de adição e subtração matricial de maneira computacional. A soma e a subtração entre duas Matrizes 59 matrizes exigem apenas que a ordem destas seja igual, visto que, para a obtenção do resultado, será necessário somar ou subtrair, respecti- vamente, termo a termo dessas matrizes. A soma de duas matrizes A = [aij] e B = [bij] de ordem m por n é uma matriz C = [cij], tal que cij = aij + bij. a a a a b b b b an n mn n n mn 11 1 1 11 1 1 1� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 11 11 1 1 1 1 � � � � � � � � � � � � � � b a b a b a b n n n n mn mn � � � � � Para compreender essa operação, acompanhe o exemplo a seguir. Exemρlo 1 Sejam as matrizes A �e�B �� � � � � � � � � � � � � � 1 2 3 4 4 5 6 7 , então: A B� � � � � � � � � � � � � � � � � � � 1 4 2 5 3 6 4 7 5 7 9 11 A mesma propriedade é válida para a subtração entre matrizes, como podemos notar no exemplo a seguir. Exemρlo 2 Sejam as matrizes A �e�B� � � � � � � � � � � � � � 1 2 3 4 4 5 6 7 , então: A B� � � � � � � � � � � � � � � � � � � � � � � 1 4 2 5 3 6 4 7 3 3 3 3 Contudo, o processo de multiplicação não é tão intuitivo. Por esse motivo, apresentamos, na sequência, o algoritmo que permite fazermos multiplicações entre duas matrizes. 60 Matemática para Computação Algoritmo 1 Sejam A = [aij]m⨯n e B = [brs]n⨯p, o produto de A por B é definido como AB = [cuv]m⨯p onde c a b a b a buv k n uk kv u v un nv� � ��� � � 1 1 1 O produto entre duas matrizes Am⨯n e Bl⨯p só é possível se o número de colunas da matriz A for igual ao número de linhas da matriz B, n = l. O resultado desse produto será uma matriz de ordem m ⨯ p. O elemento resultante desse produto será denotado por cij (i-ésima linha e j-ésima coluna da matriz produto) e obtido por meio da soma en- tre os produtos dos elementos da i–ésima linha da primeira matriz pelos elementos correspondentes da j–ésima coluna da segunda matriz. Acompanhe o exemplo a seguir para compreender melhor como calculamos a multiplicação de matrizes. Exemρlo 3 Vamos efetuar o produto entre as matrizes A1⨯2 = [–1 1] e B2 3 2 1 4 3 4 3� � � � � � � � � � � . Verificamos se o número de colunas da matriz A é igual ao número de linhas da matriz B. Nesse caso: colunas de A = linhas de B = 2 Portanto, o produto entre matrizes é possível e dará origem a uma matriz C, com o número de linhas de A e o número de colunas de B, ou seja, originará uma matriz C1⨯3. C1 3 1 1 2 1 4 3 4 3� � ��� �� � � � � � � � � � � = [(–1) · 2 + 1 · 3 (–1)(–1) + 1 · 4 (–1)(–4) + 1 · (–3)] = [1 5 1] m yd eg ag e/ Sh ut te rs to ck Matrizes 61 A multiplicação de matrizes tem as seguintes propriedades: • Em geral, AB ≠ BA. • AB = 0, sem que A = 0 ou B = 0. • AI = IA = A, onde I é a matriz identidade. • Distributividade: • A(B + C) = AB + AC; • (A + B)C = AC + BC; • (AB)C = A(BC). • A(AB)t = BtAt. • 0A = 0 e A0 = 0. Fechamos esta seção com as propriedades algébricas da multipli- cação entre matrizes. Com isso, temos em mãos as propriedades ma- triciais necessárias para resolvermos diversos exemplos e aplicações. 3.3 Bases Vídeo Vimos que uma matriz é constituída de linhas e colunas. Essas mesmas linhas e colunas podem ser consideradas vetores dessa matriz. Observe a Figura 3, que apresenta, graficamente, duas equações de retas, representadas em um mesmo sistema de coordenadas cartesianas, ℝ². Figura 3 Sistema de equação 2 4 3 2 x y x y � � � � � � � 3,5 4 3,5 4,5 5,5–3,5 –3 –2,5 –2 –1,5 –1 –0,5 0 3 3 4 5 6 X Y 2,5 2,5 2 2 1,5 1,5 1 1 –1 0,5 0,5 0,5 eq2: 3x – y = 2eq1: 2x + y = 4 eq1 eq2 Fonte: Elaborada pela autora. 62 Matemática para Computação Esse sistema, escrito como 2 4 3 2 x y x y � � � � � � � �� , pode ser representado na forma matricial a seguir: 2 1 3 1 4 2� � � � � � � � � � � � � � � � � � � � x y Ao analisarmos os vetores linha da matriz dos coeficientes, dados por v1 = [2, 1] e v2 = [3, –1], podemos expressar que v1 não pode ser escrito como uma combinação linear de v2, ou seja, não podemos de- notar como v1 ≠ αv2. Essa simples análise nos fornece a informação de que esses veto- res são linearmente independentese, como eles são formados por duas coordenadas, isto é, são bidimensionais e estão contidos em um espaço bidimensional, ainda podemos afirmar que esses mesmos dois vetores, v1 e v2, formam uma base para o ℝ2. No caso de um sistema de equações composto por n equações e n variáveis, identificar que os vetores que formam a matriz dos coefi- cientes são, também, uma base para ℝn nos permite afirmar que esse sistema é compatível e determinado, então tem uma única solução. Assim, para identificar se n vetores de uma matriz formam uma base para o espaço ℝn, precisamos analisar duas situações: I. se os vetores são linearmente independentes (LI); II. se os vetores geram ℝn. A base mais simples para um espaço de vetores é a base canôni- ca. Para o ℝ², ela é formada pelos vetores e1 = (1, 0) e e2 = (0, 1). Note que, se admitirmos um outro vetor qualquer nesse sistema, por exem- plo, o vetor v = (–5, 3), este será escrito como uma combinação linear (Figura 4) de e1 e e2 na forma: (–5, 3) = –5(1, 0) + 3(0, 1) = –5v1 + 3v2 Geometricamente, o que estamos mostrando é que existem escala- res α1 = –5 e α2 = 3, tais que v = α1 v1 + α2 v2. Trouxemos o conceito de base pensando na proposta aplicada, mas, caso você tenha interesse em se aprofundar nesse tema, com a visão da álgebra linear, sugerimos o vídeo Combinações li- neares, subespaços gerados e bases | A essência da Álgebra Linear, capítulo 2, publicado pelo canal 3Bluw1Brown. Disponível em https://www.youtu- be.com/watch?v=k7RM-ot2NWY. Acesso em: 6 jul. 2021. Vídeo https://www.youtube.com/watch?v=k7RM-ot2NWY https://www.youtube.com/watch?v=k7RM-ot2NWY Matrizes 63 Figura 4 Combinação linear entre v1 e v2 y x 3v2 v2 = (0, 1) v1 = (1, 0) –5v1 Fonte: Elaborada pela autora. Portanto, uma combinação linear pode ser definida como: Definição 2 Sejam v1, ..., vn elementos de um espaço de vetores V, então v é uma combinação linear de v1, ..., vn se existirem números reais α1, ... ,αn, tais que: v = α1v1 + ... + αnvn (1) Já o que define a independência linear é: Definição 3 Uma sequência de vetores v1, ..., vn de um espaço vetorial V é linearmente independente (LI) se: α1v1 + ... + αnvn = 0 (2) e isso só é verdade se α1 = ... = αn = 0. Se dispusermos os vetores que desejamos analisar em uma matriz quadrada A, como fizemos com a matriz dos coeficientes do sistema de equações anterior, e calcularmos seu determinante, podemos ter dois tipos de solução: • se det A = 0, então os vetores são LD; • se det A ≠ 0, então os vetores são LI. LD: linearmente dependente. Glossário 64 Matemática para Computação Para compreender esses conceitos, acompanhe o próximo exemplo. Exemρlo 4 Sejam os vetores u = (1, 2, 3), v = (3, –1, 6) e w = (4, 2, 1). Queremos classificar os três vetores em LI ou LD. Assim, fazemos: A � � 1 2 3 3 1 6 4 2 1 Aplicando a regra de Sarrus, podemos escrever: A � � � � �� � � � � � � � � � �� � � � � � � � � � 1 2 3 3 1 6 4 2 1 1 1 1 2 6 4 3 3 2 4 1 3 2 6 1 1 3 2 59 Logo, os vetores u, v e w são linearmente independentes, pois o determinante de A resultou em um valor diferente de zero. Portanto, pode-se usar as matrizes e suas operações – nesse caso, o determinante – para analisar se os vetores que a compõem são linearmente independentes. Conhecendo a quantidade de elementos que está alocada nesses vetores e a dimensão do espaço a ser analisa- do, é possível avaliar se esse espaço pode ser gerado por esses veto- res. Com essas duas conclusões em mãos, podemos afirmar (ou não) a existência de uma base de vetores para o espaço avaliado. 3.4 Fatoração matricial – Método de Gauss Vídeo Computacionalmente, podemos trabalhar com matrizes com um número muito grande de elementos. Ao pensarmos, por exemplo, na análise de dados, nas redes de computadores ou mesmo na área de inteligência artificial, o número de elementos em uma matriz pode estar na casa dos milhares ou mais. Portanto, é impossível realizarmos cálculos de maneira manual, sem a utilização de uma ferramenta computacional. Matrizes 65 Dessa forma, a correta manipulação desses dados dentro das matri- zes é fundamental para que encontremos resultados coerentes. Assim, vamos abordar, nesta seção, a fatoração (decomposição) de matrizes, para que possamos viabilizar algoritmos que nos permitam resolver determinantes, encontrar a inversa ou mesmo resolver gran- des sistemas de equações, dentre outras aplicações. Seja uma matriz Am⨯n dada por: A a a a a a a a a k m n k 1 1 1 11 1 12 1 1 1 1 1 1 1 21 1 22 2 � � � � � � � � � � � � � � � � � � � � � � � � aa a a a a a a m n kk km kn 2 2 1 1 2 1 1 1 1 1 1 � � � � � � � � � � � � � � � � � � � � � � � � � � � � � k k �� � � � � � � �a a a a amk mm mnm m1 1 2 1 1 1 1� � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� � � � � E, ainda, seja A(k) uma matriz semelhante a A(1), já triangularizada: A a a a a a a a a k k m n k m � � � � � � � � � � � � � � � � � � 11 1 12 1 1 1 1 1 1 1 22 2 2 2 2 20 � � � � � �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � a a a a a n kk k km k kn k mk k 2 2 0 0 0 0 aa amm k mn k� � � � � � � � � � � � � � � � � � � � � � � � � � � �� A triangularização de matrizes é um dos processos mais práticos para a resolução de diversos problemas dentro da álgebra, como aque- les citados anteriormente. Vamos entender esse processo de modo que seja possível transcrevê-lo em formato de algoritmo. Note que: A M A A M Am m m 2 1 1 1 1 � � � � � � � �� � � � � � � � �� � � � Portanto, precisamos de m – 1 passos para concluir a decomposi- ção. Vamos escrever esse processo em etapas. 66 Matemática para Computação Se a11 1 0� � � , então: A = A a a a a a a a a 1 k m n k � � � � � � � � � � � � � � � � � 11 1 12 1 1 1 1 1 1 1 21 1 22 2 1 � � � � 11 1 1 1 1 1 2 2 1 1 2 1 � � � � � � � � � � � � � � � � � � � � � � � � � � � � a a a a a a a m n kk km knk k �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �a a a a amK mm mnm m1 1 2 1 1 1 1 �� � � � � � � � � Assim, existe uma matriz M1 (m⨯m): M a a a a m 1 21 1 11 1 1 1 11 1 1 1 1 1 1 1 � � � � � � � � � � � � � � � � � � � � � � � � � � � � .. .. .. �� � � � � � � � � � � � � Com: m a a � ��m a a � �m a a m m 21 21 1 11 1 31 31 1 11 1 1 1 1 11 1 � � � � � � � � � � � � � � � � � , , , �� � � � � �� �, .��tal�que�A M A2 1 1 Logo: A a a a a a a a a k m n k m 2 11 1 12 1 1 1 1 1 1 1 22 2 2 2 2 20 � � � � � � � � � � � � � � � � � � � � � � � �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � a a a a a a n k kk km kn m 2 2 2 2 2 2 2 2 2 0 0 �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� � �a a amk mm mn 2 2 2 Note que M1 multiplica todas as colunas de A, mas só zera a coluna 1, abaixo da posição (1, 1), ou, ocasionalmente, alguma outra coluna. De si gn -S py /S hu tte rs to ck PASSO 1 Matrizes 67 Se a22 2 0� � � , então existe uma matriz M2 (m⨯m), tal que A(3) = M2 · A(2) = M2 · M1 · A(1). M a a a a m 2 32 2 22 2 2 2 22 2 1 1 1 1 1 1 � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� � � � � � � � Com: m a a � ��m a a � �m a a� m m 32 32 2 22 2 42 42 2 22 2 2 2 2 � � � � � � � � � � � � � � � � , , ..., 222 2� � . Logo: A a a a a a a a a k m n k m 3 11 1 12 1 1 1 1 1 1 1 22 2 2 2 2 20 � � � � � � � � � � � � � � � � � � � � � � � �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � a a a a a n kk km kn mk 2 2 3 3 3 3 0 0 0 0 aa amm mn 3 3� � � � � � � � � � � � � � � � � � � � � � � � � � � �� PASSO 2 De si gn -S py /S hu tte rs to ck Se akk k� � � 0, então A(k+1) = Mk · A(k). A a a a a a a a ak k n k n �� � � � � � � � � � � � � � � � �1 11 1 121 1 1 1 1 22 2 2 2 2 20 � � � � � � � kkk k kn k k k k k n k m k a a a a � � � � � � �� � � �� � � � � � � � � � 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 , , , 11 1 1k m n ka�� � �� � � � � � � � � � � � � � � � � � � � � � � � � �� , O processo deve ser seguido até o passo r, em que r = min{m – 1, n}. Dessa forma, podemos escrever: A(k+1) = Mk · A (k) = Mk · Mk–1 · ... · M1 · A (1). De si gn -S py /S hu tte rs to ck PASSO K 68 Matemática para Computação Mas por que todo esse procedimento? Porque sabemos que o determinante de uma matriz pode ser calculado por meio da multipli- cação dos elementos da diagonal principal; porém, também, porque usaremos métodos de decomposição aplicados a outras operações com matrizes, por exemplo, no cálculo da inversa de uma matriz. Além disso, outro motivo é o computador resolver processos numéricos discretos, por etapas, podendo, ainda, carregar muitos erros (de arre- dondamento, truncamento e cancelamento). Dessa forma, para implementar uma matriz e as operações sobre esta, é necessário que tenhamos um passo a passo do processo numé- rico. Transformar um problema matemático em um algoritmo nos ofe- rece justamente esse passo a passo necessário para que o computador possa resolvê-lo. Agora, vamos colocar na prática os passos observados na teoria. Exemρlo 5 Seja A � � � � � � � � � � � � � � 2 4 2 1 1 5 4 1 2 . A decomposição de Gauss ocorrerá em r = min{2, 3} = 2 passos. Então, fazendo o passo a passo, temos: • Passo 1: a11 ≠ 0 M1 1 0 0 1 2 1 0 4 2 0 1 � � � � � � � � � � � � � � � � � � � A M A2 1 1 1 0 0 1 2 1 0 4 2 0 1 2 4 2 1 1 5 4 1 2 � � � �� � � � � � � � � � � � � � � � � � � � � � � � � � � � �� � � � � � � � � � � � � � � � � � � � � 2 4 2 0 3 6 0 7 2 Cada algoritmo precisa ser adaptado para uma linguagem de programa- ção específica. Se utili- zarmos uma linguagem de alto nível, possivelmente, a própria linguagem já tra- ga de maneira intrínseca questões como armaze- namento dos dados de uma matriz na memória, módulos de inversão, cálculo do determinante etc. Mas, se for uma linguagem de baixo nível, todas essas questões serão declaradas pelo programador. Sugerimos a leitura dos seguintes materiais, que trazem um pouco da programação usada em Python (alto ní- vel) e em C++ (baixo nível) em casos de aplicações que usam matrizes: • Aulas de introdução à computação com Python: matrizes. Disponível em: https://panda.ime.usp. br/aulasPython/static/aulasPython/ aula11.html. Acesso em: 6 jul. 2021. • Curso de C: matrizes. Disponível em: http://mtm.ufsc. br/~azeredo/cursoC/aulas/c530. html. Acesso em: 6 jul. 2021. Leitura https://panda.ime.usp.br/aulasPython/static/aulasPython/aula11.html https://panda.ime.usp.br/aulasPython/static/aulasPython/aula11.html https://panda.ime.usp.br/aulasPython/static/aulasPython/aula11.html http://mtm.ufsc.br/~azeredo/cursoC/aulas/c530.html http://mtm.ufsc.br/~azeredo/cursoC/aulas/c530.html http://mtm.ufsc.br/~azeredo/cursoC/aulas/c530.html Matrizes 69 • Passo 2: a22 ≠ 0 M2 1 0 0 0 1 0 0 7 3 1 � � � � � � � � � � � � � � � � A M A3 2 2 1 0 0 0 1 0 0 7 3 1 2 4 2 0 3 6 0 7 2 � � � �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� � � � � � � � � � � � � � � � � 2 4 2 0 3 6 0 0 12 Os elementos akk k� � são os elementos pivôs. O resultado obtido com o método de Gauss pode ser aplicado em muitos contextos, como citamos anteriormente. Usando esse método como “motor” para as nossas próximas de- composições, vamos ver algumas possibilidades para a decomposição matricial que podem agilizar o processo de cálculo computacional e mi- nimizar os erros obtidos nesse processo. 3.5 Decomposição LU e LDU Vídeo Nesta seção, apresentaremos alguns tipos de fatoração de matrizes que serão úteis para a resolução de sistemas de equações lineares. Esses processos de fatoração também são chamados de méto- dos de decomposição. Iremos, então, estudar a decomposição LU e a LDU. Esse último método ainda pode ser ramificado em outros mé- todos, dependendo do tipo de matriz que tivermos. Vamos entender esses processos. 3.5.1 Decomposição LU Seja uma matriz A de ordem m. A decomposição dessa matriz em outras duas matrizes, sendo a primeira uma matriz triangular infe- rior L (lower) e a segunda uma matriz triangular superior U (upper), é chamada de decomposição LU (FRANCO, 2006). 70 Matemática para Computação A a a a a l l l um m mm m mm � � � � � � � � � � � � � � � � � � � � � � 11 1 1 11 1 110� � � � � � � � � � �� � � � � u u L U m mm 1 0 � � � � � � � � � � � � Esse tipo de decomposição não é único. Ou seja, podem existir dife- rentes matrizes triangulares inferiores e superiores que, quando mul- tiplicadas, originarão a matriz A. Assim, para encontrá-las, usamos o processo de eliminação de Gauss, que nos auxilia a escrever a matriz A na forma fatorada em matrizes mais simples. É possível ter uma ideia da aplicação desse tipo de decomposição com a leitura do artigo Estimação de estado em sistemas elétricos de potência: meto- dologia para análise de observabilidade considerando medidas convencionais e fasoriais. Nesse artigo, os autores fazem uso do método LU para tratar o problema real transformado em modelo matemático. Acesso em: 6 jul. 2021. https://www.researchgate.net/publication/277717877_ESTIMACAO_DE_ESTADO_EM_SISTEMAS_ELETRICOS_DE_POTENCIA_ METODOLOGIA_PARA_ANALISE_DE_OBSERVABILIDADE_CONSIDERANDO_MEDIDAS_CONVENCIONAIS_E_FASORIAIS Artigo Como vimos, o processo de Gauss gera matrizes M1, M2, ... ,Mr , com r = min{m – 1, n}, tal que: A(r+1) = Mr ⋅ Mr–1 ⋅ ... ⋅ M1 ⋅ A As matrizes M não são singulares, portanto podemos calcular suas inversas. Assim: A �M �M � � M �A r r� � � � � �� � � �� �1 1 2 1 1 1 Portanto, L M M Mr� � ��� � � � 1 1 2 1 1 e U = A(r+1), com: Triangular inferior Triangular superior L M M M m m m r r � � � � � � � � � � � � � � � � � � � � � � � 1 1 2 1 1 1 2 1 1 1 ... e U a a amm m � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 11 1 22 2 ... Para compreender como desenvolver a decomposição LU de uma matriz, acompanhe o próximo exemplo. Matrizes 71 Exemρlo 6 Seja A � � � � � � � � � � � 3 2 4 1 1 2 4 3 2 . Determine a decomposição LU da matriz A. Usando a decomposição de Gauss, temos como primeiro pivô o ele- mento na posição a11 1 3� � � . Assim, os multiplicadores são: m a a �e�m a a 21 21 1 11 1 31 31 1 11 1 1 3 4 3 � � � � � � � � � � � � . A A m m � � � � � � � � � � � � � ������ � � � 1 2 21 1 3 31 1 3 2 4 1 1 2 4 3 2 3 2 4 0 1 3 2 3 0 1 L L L L 33 10 3 � � � � � � � � � � � � � � � � � O próximo pivô é a22 2 1 3 � � � . Então, o multiplicador é m a a 32 32 2 22 2 1 3 1 3 1� � � � � � � . A L m L 2 3 32 2 3 2 4 0 1 3 2 3 0 1 3 10 3 3 2 4 0 1 3 2 3 � � � � � � � � � � � � � � � � � � � � � � ����� 00 0 4� � � � � � � � � � � � � Portanto, L carrega os multiplicadores (triangular inferior) e U é a última matriz após a triangularização (triangular superior). L �e�U� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 1 0 0 1 3 1 0 4 3 1 1 3 2 4 0 1 3 2 3 0 0 4 Além da decomposição LU, que, como vimos, não é única, pode- mos nos basear nela para um outro tipo de decomposição, chamado de LDU. Vamos entendê-lo na sequência. Na linguagem MATLAB, é possível usar as fun- ções intrínsecas dessa linguagem para calcular a decomposição LU. Assim, tendo a matriz A, basta fazer: >[L, U] = lu(A) >[L, U, P] = lu(A) Curiosidade 72 Matemática para Computação 3.5.2 Decomposição LDU A decomposição LDU, ao contrário da LU, é única, desde que os pivôs sejam diferentes de zero. Como o próprio nome nos leva a perceber, A será fatorada (decomposta) em uma matriz triangular in- ferior (L), uma matrizdiagonal (D) e uma matriz triangular superior (U) na forma: L ������D d d dnn � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 1 1 1 1 11 22 ... �� � � � � � � � � � � � � � � � � � � � � � � �����U 1 1 1 1 Gauss pode ser aplicado sem troca de linhas ou colunas. Dessa maneira, A(n) = Mn–1 · ... · M1A (1) Assim, A(n) = L–1 · A(1) = L-1 · A Portanto, A = L · A(n), em que A(n) tem todos os pivôs akk k� � � 0. Definindo D a a ann n � � � � � � � � � � � � � � � � � � � � � � � 11 1 22 2 ... , então D–1 existe e D a a ann n � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 1 11 1 22 2 1 1 1 ... Definindo U = D–1 · A(n), temos que: U a a a a a a n n� � � � � � � � � � � � � � � � � � � � � � � � � � � 1 1 1 12 1 11 1 1 1 11 1 2 2 22 2 ... �� � � � � � � � � � � � � Matrizes 73 E como: L m m mr � � � � � � � � � � � � � � � � � � � 1 1 11 2 ... Então, A = L · A(n) = L · D(D-1 · A(n)) = LDU. Assim, A pode ser decomposta da forma descrita. Acompanhe o exemplo a seguir para praticar a decomposição em LDU de uma matriz. Exemρlo 7 Decomponha a matriz A � � � � � � � � � � � � � � 1 1 2 1 5 3 4 9 1 em LDU. Para decompor a matriz A em LDU, utilizamos a decomposição de Gauss. Assim, calculamos M1 usando, inicialmente, o pivô a11 1 1� � � , e en- contramos m a a �e�m a a �21 21 1 11 1 31 31 1 11 1 1 1 1 4 1 4� � � � � � � � � � � � � � � � . Portanto, a matriz obtida é M1 1 0 0 1 1 0 4 0 1 � � � � � � � � � � � � . Desse modo, obtemos, nessa etapa, a matriz A m m 2 2 21 1 3 31 1 1 1 2 0 4 5 0 5 7 � � � � � ����� � � � � � � � � � � � � � L L L L . Agora, precisamos calcular M2 usando como pivôs �a �e�m a a 22 2 32 32 2 22 2 4 5 4 � � � � � �� � � � . Portanto, M2 1 0 0 0 1 0 0 5 4 1 � � � � � � � � � � � � � � � � . Assim, A L m L 3 3 32 2 1 1 2 0 4 5 0 0 3 4 � � � � ����� � � � � � � � � � � � � � � � � . Nesse momento, temos: A � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �1 1 2 1 5 3 4 9 1 1 0 0 1 1 0 4 5 4 1 1 1 2 0 4 55 0 0 3 4 � � � � � � � � � � � � � � � � LU 74 Matemática para Computação Agora, basta organizar U na forma: U DU*� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 1 0 0 0 5 0 0 0 3 4 1 1 2 0 1 3 5 0 0 1 Portanto, A � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 1 1 2 1 5 3 4 9 1 1 0 0 1 1 0 4 5 4 1 1 0 0 0 5 0 00 0 3 4 1 1 2 0 1 3 5 0 0 1� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � LDU Dependendo de como D é tratado, existem três tipos de decomposições: 1 2Decomposição de Doolittle (direto de Gauss) A = L · (D · U) = L · U’, em que lii = 1, ∀ i. A � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 1 1 1 ... . Decomposição de Crout A = (L · D) · U = L’ · U, em que uii = 1, ∀ i. A � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � . ... 1 1 1 3 Decomposição de Cholesky A = Q · QT, em que lii = uii, ∀ i. A x x x x x x x x � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � Observação: a decomposição de Cholesky pode ser encontrada baseada em Gauss, pois, se A é simétrica, A = LDU e U = LT. Contudo, a decomposição de Cholesky só é possível quando A for uma matriz positiva definida por A = LDLT. Se D > 0, então: D a ann 1 2 11 � � � � � � � � � � � � � � � ... ... e A L D D LT �Q Q T� � � � � � � � � � � � � � � � � �· · · · 1 2 1 2 Matrizes 75 Quando aplicamos os processos de decomposição para agilizar a resolução de sistemas de equações, percebemos que cada tipo desses sistemas se comporta melhor com uma decomposição específica. Se as matrizes são esparsas, adotamos um método; se temos uma matriz em blocos, podemos adotar outro. O importante é termos o conhecimento prévio das ferramentas que podem ser utilizadas, para que possamos definir, em cada caso, qual a melhor estratégia de resolução, considerando a agilidade, a rapidez computacional e a minimização de erros. Uma matriz é denomi- nada positiva definida se os determinantes das n submatrizes principais de A forem positivos, ou seja: |Akk| > 0, para todo 1 ≤ k ≤ n A matriz identidade é um exemplo de matriz positiva definida. Saiba mais 3.6 Inversa de uma matriz Vídeo Há algumas maneiras de calcular a inversa de uma matriz. Uma de- las exige o cálculo do determinante. Como vimos, o determinante pode ser encontrado por meio da triangularização de uma matriz. Após esse processo, basta multiplicar os elementos da diagonal resultante. Logo, pensando computacionalmente, o cálculo do determinante de uma matriz depende de operações elementares (as quais não alteram a solução do sistema) que podem ser descritas dos seguintes modos: I. Permuta da i-ésima linha pela j-ésima linha. Li ↔ Lj – é trocar as linhas, o que é equivalente a trocar a posição das equações. II. Multiplicação da i-ésima linha por um escalar não nulo λ. Li → λLi – refere-se ao mesmo que multiplicar um número não nulo na equação correspondente. III. Substituição da i–ésima linha pela i–ésima linha mais λ vezes a j–ésima linha. Li → Li + λLj – corresponde a somar o múltiplo da outra equação. Vamos praticar o cálculo do determinante de uma matriz, utilizando as operações elementares. A plataforma da Khan Academy tem um material muito interessante sobre as operações aplicadas sobre linhas e colunas de uma matriz. Além da leitura, é possível resolver alguns exercícios sobre o assunto. Disponível em: https://pt.khana- cademy.org/math/precalculus/ precalc-matrices/elementary-matrix- -row-operations/a/matrix-row-ope- rations. Acesso em: 6 jul. 2021. Saiba mais https://pt.khanacademy.org/math/precalculus/precalc-matrices/elementary-matrix-row-operations/a/matrix-row-operations https://pt.khanacademy.org/math/precalculus/precalc-matrices/elementary-matrix-row-operations/a/matrix-row-operations https://pt.khanacademy.org/math/precalculus/precalc-matrices/elementary-matrix-row-operations/a/matrix-row-operations https://pt.khanacademy.org/math/precalculus/precalc-matrices/elementary-matrix-row-operations/a/matrix-row-operations https://pt.khanacademy.org/math/precalculus/precalc-matrices/elementary-matrix-row-operations/a/matrix-row-operations 76 Matemática para Computação Exemρlo 8 Seja a matriz A � � � � � � � � � � � � � � � 2 2 3 1 1 3 2 0 1 , queremos calcular seu determinante por meio de uma triangularização. Assim, aplicando operações elemen- tares, temos: � � � � � � � � � � � � � � � ������ � � � � � � 2 2 3 1 1 3 2 0 1 2 2 3 0 0 9 2 0 3 3 1 2 2 1 2 1 L L L L L L 22 4� � � � � � � � � � � � � � � � � � � � � � � � � � � � � ����� � � � � � � � � � � � �� 2 2 3 0 0 9 2 0 2 4 2 2 3 0 2 4 0 0 9 2 3 2L L �� � � � � � � Nesse ponto, já temos uma matriz triangularizada; portanto, det A �� � � � �� � � � � � �2 2 9 2 18 . Com base nesse princípio, desenvolvemos, na sequência, o cálculo da inversa de uma matriz, conhecendo seu determinante. 3.6.1 Inversa de uma matriz por meio de determinantes Uma das maneiras de encontrarmos a inversa de uma matriz qua- drada A é por meio da matriz dos cofatores de A. Com esse resultado, é possível obter a matriz adjunta de A e, na sequência, sua matriz inversa. Dessa forma, inicialmente, precisamos conhecer o cofator de cada um dos elementos de A, dados por: Aij = (–1) i+j |Mij| Assim, Mij representa a matriz obtida da matriz original pela elimina- ção da i-ésima linha e da j-ésima coluna. É possível formar uma nova matriz, denominada de Ā, em que Ā = [Aij]. Essa será a matriz dos cofatores. Matrizes 77A transposição dessa matriz Ā origina a chamada matriz adjunta de A, denotada por adj(A). Logo: adj(A) = Āt Com o conceito de determinante de uma matriz e de matriz ad- junta, podemos enunciar um teorema que permite o cálculo da in- versa de uma matriz A baseado nesses conceitos. Teorema 1 Uma matriz quadrada A admite uma inversa se, e somente se, det (A) ≠ 0 (KOLMAN; HILL, 2013). Nesse caso: A A adj A� � � � � �� � 1 1 det Assim como as propriedades para as operações entre matrizes ou mesmo as propriedades para o determinante de uma matriz, destinamos, nesta seção, um espaço para tratarmos das proprie- dades das matrizes invertíveis. São elas: • Sejam duas matrizes quadradas A e B, de ordem n, com deter- minante diferente de zero e, portanto, não singulares – o que nos permite afirmar que são invertíveis. Portanto, se existe A–1 e B–1, então A · B é invertível e (A · B)–1 = B–1 · A–1. • Seja A uma matriz quadrada, de ordem n, com BA = I, portan- to B é, também, de ordem n. Logo, A é invertível, ou seja, A–1 existe e, além disso, B = A–1. • Dizemos que uma matriz A é semelhante a uma matriz B se, e somente se, existir uma matriz invertível Q, tal que podemos escrever A = Q–1 BQ. Em todos os casos, podemos usar essas características algébri- cas para otimizar os processos numéricos e agilizar a obtenção de uma resposta. Computacionalmente, encontramos muitas vantagens quando podemos simplificar processos, e uma delas é a possibilidade de diminuir o custo computacional. Ainda, é possível minimizar erros quando reduzimos a quantidade de operações realizadas. Dessa forma, o estudo das matrizes invertíveis e suas propriedades nos traz um ganho em diferentes áreas e aplicações. 78 Matemática para Computação 3.6.2 Inversa de uma matriz por meio do método de Gauss-Jordan Vamos supor que uma matriz A, de ordem n, possa ser fatorada até ser equivalente à matriz identidade: In = Mk · Mk–1 · ... · M2 · M1 · A Sendo assim, podemos multiplicar os dois lados da igualdade para obtermos a matriz inversa de A, ou seja: (In) · A –1 = (Mk · Mk–1 · ... · M2 · M1 · A) · A –1 A–1 = (Mk · Mk–1 · ... · M2 · M1) · In Na prática, se temos uma matriz A, de ordem n, podemos escrever essa matriz da forma: [A│I]n⨯2n Aplicando operações elementares sobre [A│I]n⨯2n, precisamos obter [I│B]n⨯2x com B = A–1. Uma observação: se, ao realizar o procedimento, ocorrer uma linha de zeros do lado esquerdo, significa que a matriz A não tem inversa. Para comprovar esse resultado, basta calcular o determinante de A e verificar que ele é igual a zero. O exemplo a seguir esclarece como encontrar a inversa de uma ma- triz por meio da triangularização, ou seja, pelo método Gauss-Jordan. Exemρlo 9 Encontre a inversa de 2 6 1 3� � � � � � � . Aplicando algumas operações elementares nessa matriz, obtemos: 2 6 1 3 1 0 0 1 1 3 1 3 1 2 0 0 112 2 1� � � � � � � � �� � � � � � � � � � � � � ��� � � � � �L L L | | | | �� � � � � � � � � � � � � � � 1 3 1 6 1 2 0 1 2 1 � � | | O material sobre inversão de matrizes do professor Rodney Josué Biezuner tem muitos exemplos resolvidos. Sugerimos a leitura deste mate- rial, além de refazer os exemplos e exercícios presentes no texto. Disponível em: http://150.164.25.15/~rodney/ notas_de_aula/matrizes_inversas. pdf. Acesso em: 17 jun. 2021. Saiba mais http://150.164.25.15/~rodney/notas_de_aula/matrizes_inversas.pdf http://150.164.25.15/~rodney/notas_de_aula/matrizes_inversas.pdf http://150.164.25.15/~rodney/notas_de_aula/matrizes_inversas.pdf Matrizes 79 L L L � � � � 2 6 3 2 1 1 3 0 1 1 2 0 1 12 1 6 1 0 0 1 1 � � � � ��� � � � � � � � � � � � � � � ���� | | | | 44 1 2 1 12 1 6 � � � � � � � � � � � � � Portanto, A� � � � � � � � � � � � � � � 1 1 4 1 2 1 12 1 6 Com essas técnicas, relembramos os conceitos de vetores e matrizes, além de fazermos a manipulação de operações sobres essas estruturas. Percebam que o nosso foco foi trazer novas ferramentas e abor- dagens que se adequem, de maneira mais suave, à necessidade de aplicação computacional dos conceitos matemáticos. Desse modo, são abordagens que, quando transformadas em algo- ritmos, podem ser implementadas com facilidade, sendo que algumas linguagens de programação já têm essa base matemática implemen- tada para uso direto das operações. Mesmo nesses casos, é importante saber o que está acontecendo por trás da resposta obtida. Por esse motivo, sempre estimulamos que os conceitos matemáticos envolvidos nas funções intrínsecas a cada uma das linguagens de programação sejam avaliados antes do seu uso. CONSIDERAÇÕES FINAIS Neste capítulo, recordamos alguns conceitos estudados no ensino médio e fundamental e aprendemos algumas teorias ainda não trabalha- das no ensino básico. O conceito de matriz é peça fundamental para a programação. Acre- ditamos que o tripé teoria, prática e aplicação é necessário para a boa compreensão de qualquer conceito ou disciplina. Por isso, sugerimos que resolva os exercícios encontrados nas obras de referência bibliográfica, acesse os links indicados como complementação do conteúdo e resolva o máximo de exercícios possível sobre o tema. 80 Matemática para Computação ATIVIDADES Nas regras do xadrez, cada peça tem uma movimentação possível. Por exemplo, o cavalo só pode se movimentar em “L”, ou seja, • duas casas para a direita (ou para a esquerda) e uma para frente (ou para trás); • uma casa para a direita (ou para a esquerda) e duas casas para frente (ou para trás). A figura a seguir é um exemplo das possíveis movimentações que um cavalo na casa 4D pode fazer. 8 7 6 5 4 3 2 1 HGFEDCBA Explique, usando a notação “linha-coluna”, as possíveis movimentações do cavalo branco que está na casa 1G (observação: ele não pode ficar sobre outra peça branca). Atividade 1 De acordo com o conceito de base para um espaço de vetores, indique dois conjuntos de vetores que formam uma base para o ℝ³. Justifique o porquê dessas escolhas. Atividade 2 Explique por que afirmamos que a decomposição LU não é única. Atividade 3 REFERÊNCIAS FEOFILOFF, P. Vetores. IME, 2018. Disponível em: https://www.ime.usp.br/~pf/algoritmos/ aulas/array.html. Acesso em: 6 jul. 2021. FRANCO, N. M. B. Cálculo numérico. 1. ed. São Paulo: Pearson Universidades, 2006. KOLMAN, B.; HILL, D. R. Álgebra linear com aplicações. 9. ed. Rio de Janeiro: Livros Técnicos e Científicos, 2013. LEON, S. J. Álgebra linear com aplicações. 9. ed. Rio de Janeiro: Livros Técnicos e Científicos, 2019. Sistemas de equações lineares 81 4 Sistemas de equações lineares Os sistemas de equações são encontrados em uma gama de apli- cações e nas mais diversas áreas. Das exatas às ciências biológicas, passando pelas áreas tecnológicas e ciências sociais, resolver um sis- tema de equações pode nos levar a resultados de balanceamentos químicos, respostas de sistemas elétricos, equilíbrio de forças, distri- buições de alimentos, dentre tantos outros. De maneira mais conceitual, porém ainda aplicada, os sistemas de equações nos permitem encontrar o que se relaciona nas diferentes estruturas que os compõem, ou seja, pontos de intersecção, retas co- muns ao sistema e planos que se interceptam. Para resolver um sistema de equações, existem diversos métodos, desde diretos e iterativos até exatos ou com solução aproximada, mas, em todos os casos, se queremos expandir o conjunto de aplicações, precisamos levar esses modos de resolução para um aspecto computa- cional. Esse é o tema do capítulo sobre sistemas de equações lineares. Com o estudo deste capítulo, você será capaz de: • analisar a equivalência entre sistemas de equações lineares e aplicar operações elementares sobre eles; • resolver sistemas de equações de maneira direta e iterativa; • analisar alguns algoritmos de resolução de sistemas de equa- ções lineares, para incentivar o pensamento computacional; • compreender as propriedadesinerentes aos sistemas trian- gulares ou triangularizados; • classificar os sistemas de equações lineares. Objetivos de aprendizagem 82 Matemática para Computação 4.1 Sistemas equivalentes e operações Vídeo Aprender a resolver os mais diversos tipos de sistemas de equações, de maneira exata ou aproximada, é uma tarefa de grande necessidade dentro das ciências. Antes de discorrermos sobre as diferentes aborda- gens e métodos de resolução, discutiremos, nas subseções a seguir, sobre a estrutura de um sistema de equações lineares e como podemos realizar operações nesse tipo de sistema. 4.1.1 Sistemas equivalentes Analisar a equivalência entre objetos é compará-los, dois a dois, de acordo com algumas propriedades. A definição de sistemas equivalen- tes está descrita a seguir. Definição 1 “Dois sistemas de equações lineares envolvendo as mesmas variáveis são equivalen- tes se, e somente se, tiverem o mesmo conjunto solução” (LEON, 2019, p. 4). Dessa maneira, vamos supor um sistema AX1 = B e um segundo sis- tema QX2 = C. Se X1 = X2, os dois sistemas serão equivalentes. Exemρlo 1 O sistema 3 4 2 8 2 1 1 2 3 1 2 3 2 3 x x x x x x x x � � � � � � � � � � � � � � � �� é equivalente ao sistema 3 4 2 4 3 1 3 26 3 3 2 12 1 2 3 2 3 3 x x x x x x � � � � � � � � � � � � � � � � �� , pois ambos apresentam como solução o vetor X � � � � � � � � � � � � � � � � � � � � � 23 2 9 2 8 . A definição e o exemplo nos levam a pensar que, se temos um siste- ma no qual A é uma matriz complicada de ser resolvida, ou seja, exige Sistemas de equações lineares 83 muitos cálculos, podemos transformá-la em uma matriz semelhante, mais simples, por exemplo, uma matriz triangular, de modo que não alteremos a solução do sistema. Dessa maneira, temos na definição de matrizes equivalentes uma fer- ramenta essencial para nos auxiliar na resolução de sistemas de equações. Mas quais são as operações que podem ser aplicadas para essa transformação na matriz sem que o sistema seja alterado? No tópico a seguir, vamos apresentar as operações e aplicar em alguns exemplos. 4.1.2 Operações elementares Um dos modos mais rápidos de encontrar o conjunto solução para um sistema de equações lineares é por meio do chamado escalonamen- to da matriz ampliada. Uma matriz é denominada escalonada quando o número de zeros ao lado esquerdo do primeiro elemento não nulo da linha aumenta a cada linha. Por exemplo, a matriz a seguir está escalonada. 1 2 0 1 0 2 0 1 0 0 1 0 0 0 0 3 � � � � � � � � � � � � � � No caso de ter esgotado o número de colunas, isto é, quando uma linha se torna nula, todas as linhas seguintes devem ser linhas nulas. Para obter uma matriz escalonada, com base em uma matriz amplia- da do sistema de equações lineares, utilizamos operações elementares, como a seguir. O vídeo Exemplo prático: sistemas equivalentes de equações, da plataforma Khan Academy, é um conteúdo interessante sobre o tema sistemas de equações. Além de assistir ao vídeo, você pode resol- ver exercícios usando a plataforma, que é gratuita, gamificada e adaptativa. Essa prática te ajudará a fixar o conteúdo. Disponível em: https://pt.kha- nacademy.org/math/algebra/ systems-of-linear-equations/ equivalent-systems-of-equa- tions/v/identifying-equivalent- -systems-of-equations. Acesso em: 14 jun. 2021. Vídeo Permuta da i-ésima linha pela j-ésima linha. A troca de linhas corresponde à troca de posição das equações, o que não influencia na solução do sistema. Li ↔ Lj Multiplicação da i-ésima linha por um escalar não nulo λ. Equivale a multiplicar um número não nulo na equação correspondente, que também não altera a solução. Li → λLi Substituição da i-ésima linha pela i-ésima linha mais λ vezes a j-ésima linha. Equivale a somar o múltiplo da outra equação, que também não altera a solução do sistema.dav oo da / S hu tte rs to ck https://pt.khanacademy.org/math/algebra/systems-of-linear-equations/equivalent-systems-of-equations/v/identifying-equivalent-systems-of-equations https://pt.khanacademy.org/math/algebra/systems-of-linear-equations/equivalent-systems-of-equations/v/identifying-equivalent-systems-of-equations https://pt.khanacademy.org/math/algebra/systems-of-linear-equations/equivalent-systems-of-equations/v/identifying-equivalent-systems-of-equations https://pt.khanacademy.org/math/algebra/systems-of-linear-equations/equivalent-systems-of-equations/v/identifying-equivalent-systems-of-equations https://pt.khanacademy.org/math/algebra/systems-of-linear-equations/equivalent-systems-of-equations/v/identifying-equivalent-systems-of-equations https://pt.khanacademy.org/math/algebra/systems-of-linear-equations/equivalent-systems-of-equations/v/identifying-equivalent-systems-of-equations 84 Matemática para Computação Li → Li + λLj As operações realizadas em uma matriz ampliada resultam em uma matriz equivalente. Conforme o exemplo a seguir ilustra. Exemρlo 2 O sistema 3 4 2 8 2 1 1 2 3 1 2 3 2 3 x x x x x x x x � � � � � � � � � � � � � � � �� , apresentado no Exemplo 1, pode ser escrito na forma de matriz ampliada como 3 1 4 1 1 1 0 2 1 2 8 1 3 1 4 0 4 3 1 3 0 2 1 2 26 3 1 2 1 3 1 � � � � � � � � � � � � � � � � ���� � � � �L L �� � � � � � � � � � � � � � Aplicando as operações anteriormente elencadas, fazemos 3 1 4 1 1 1 0 2 1 2 8 1 3 1 4 0 4 3 1 3 0 2 1 2 26 3 1 2 1 3 1 � � � � � � � � � � � � � � � � ���� � � � �L L �� � � � � � � � � � � � � � Na sequência, desenvolvemos 3 1 4 0 4 3 1 3 0 2 1 2 26 3 1 3 1 4 0 4 3 1 3 0 0 3 3 3 2 2 � � � � � � � � � � � � � � � � � � ���� � � �L L 22 12 2 26 3 � � � � � � � � � � � � � � � � Note que, após a aplicação de operações elementares, obtemos uma matriz ampliada escalonada, sendo que podemos transcrevê-la da forma matricial para a forma de sistema. 3 4 2 4 3 1 3 26 3 3 2 12 1 2 3 2 3 3 x x x x x x � � � � � � � � � � � � � � � � �� De acordo com Leon (2019), dois sistemas que possuem matrizes ampliadas equivalentes têm o mesmo conjunto solução. Dessa manei- ra, podemos definir: Sistemas de equações lineares 85 Definição 2 “Desde que possuam matizes ampliadas equivalentes, os sistemas podem ser deno- minados sistemas equivalentes” (LEON, 2019, p. 4). Uma importante característica dos sistemas de equações lineares é a possibilidade de verificação da solução (prova real). Para isso, basta substituirmos a solução encontrada nas equações originais, como é de- senvolvido no exemplo a seguir. Exemρlo 3 No Exemplo 1, afirmamos que os sistemas 3 4 2 8 2 1 1 2 3 1 2 3 2 3 x x x x x x x x � � � � � � � � � � � � � � � �� e 3 4 2 4 3 1 3 26 3 3 2 12 1 2 3 2 3 3 x x x x x x � � � � � � � � � � � � � � � � �� eram equivalentes porque tinham a mesma solução. Assim, verificamos que eles realmente têm essa característica. Como X � � � � � � � � � � � � � � � � � � � � � 23 2 9 2 8 , então, substituindo essa solução no primeiro sistema, temos que 3 23 2 9 2 4 8 2 23 2 9 2 8 8 2 9 � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 22 8 1� � � � � � � � � � � � � � � �� � � � � � �� E o mesmo pode ser feito no segundo sistema: 3 23 2 9 2 4 8 2 4 3 9 2 1 3 8 26 3 3 2 � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 88 12� � � � � � � �� � � � � � �� Como ambos os sistemas têm X como solução, eles são sistemas equivalentes. 86 Matemática para Computação Com os sistemas equivalentes e operações definidos, veremos na sequência a aplicação de inversão de matrizes para a solução de um sistema de equações. 4.1.3 Análise da matriz inversa Um sistema linear da forma AX = B com A sendo uma matriz de coefi- cientes quadrada pode ser resolvido com a aplicação de matrizes inversas. Note que, para esse tipo de aplicaçãoser possível, devemos ter sis- temas de equações bem específicos (com n equações e n variáveis). Outra questão importante é a necessidade de que A seja invertível, ou seja, que tenha det A ≠ 0. Se essas exigências são verificadas, podemos escrever: Definição 3 Seja A uma matriz n⨯n com A invertível, então é válida a sequência de cálculos a seguir: I. AX = B. II. A-1 · (AX) = A-1 · B. III. In · X = A-1 · B. IV. X = A-1 · B. Portanto, se A cumpre essas condições, temos que X = A-1 · B será a solução única para o sistema determinado. 4.2 Sistemas triangulares e escalonados Vídeo O processo que permite o escalonamento de uma matriz tem como fundamentação teórica o método de Gauss (fatoração ou eliminação gaussiana), que nos permite escrever um sistema de equações lineares na sua forma triangular superior. Por meio de um sistema de equações lineares na forma triangula- rizada (inferior ou superior), é possível encontrar a solução utilizando substituições progressivas (triangular inferior) ou regressivas (triangu- lar superior). Vamos entender esse processo. No vídeo Testando uma solução para um sistema de equações, do canal da Khan Academy Brasil, você poderá rever esse procedimento sendo aplicado em outros siste- mas de equações. É uma ferramenta poderosa para verificar se a solução encontrada está correta. Disponível em: https://youtu.be/ sxJHonr96kA. Acesso em: 14 jun. 2021. Vídeo Sugerimos que você assis- ta ao vídeo Escalonamento, disponível no canal Portal da Matemática OBMEP. Com ele, é possível reca- pitular a decomposição gaussiana e começar a aplicá-la no contexto dos sistemas de equações lineares. Disponível em: https://www.youtu- be.com/watch?v=QmmYqR-7zm4. Acesso em: 14 jun. 2021. Vídeo https://youtu.be/sxJHonr96kA https://youtu.be/sxJHonr96kA https://www.youtube.com/watch?v=QmmYqR-7zm4 https://www.youtube.com/watch?v=QmmYqR-7zm4 Sistemas de equações lineares 87 Seja um sistema de equações lineares da forma LX = B, com • L l � l ln nn � � � � � � � � � � � 11 1 0� � � � � • X x xn � � � � � � � � � � � 1 • B b bn � � � � � � � � � � � 1 Portanto, esse é um sistema triangular inferior no qual a matriz dos coeficientes, L, tem seus elementos na forma lij = 0 para i < j. Portanto, l x b l x l x b l x l x l x bn n nn n n 11 1 1 21 1 22 2 2 1 1 2 2 � � � � � � � � � � � � � � � � � � � Podemos montar algoritmos para calcular a solução de sistemas li- neares com essa característica e que poderão ser reescritos na lingua- gem de programação desejada. Para estruturar tal algoritmo, usaremos uma linha genérica li, tal que li1 · x1 + li2 · x2 + ⋯ + lii · xi = bi Dessa maneira, isolando xi, obtemos x b l l x l x li i i i ii i ii � � � � � � �( )1 2 2 1 1 Portanto, podemos denotar esse raciocínio como o algoritmo a seguir. Algoritmo 1 x b l1 1 11 = Para i = 2, ..., n faça x b l x li i ij j j i ii � � � � � �� � � � ��� � � 1 1 m yd eg ag e/ Sh ut te rs to ck 88 Matemática para Computação Para compreender melhor o Algoritmo 1, acompanhe o exemplo a seguir. Exemρlo 4 Seja um sistema de equações lineares triangular inferior da forma 1 0 0 2 3 0 1 2 1 2 2 1 1 2 3 � � � � � � � � � � � � � � � � � � � � � � � � �� � � � � � � � � � x x x Vamos resolver esse sistema usando o Algoritmo 1. Assim, x b l1 1 11 2 1 2� � � � � x b l x l2 2 21 1 22 2 2 2 3 2 4 3 2� � � � �� � � � � � � � x b l x l x l3 3 31 1 32 2 33 1 1 2 2 2 1 1 2 4 1 5� � � � � �� � �� � � �� � �� � � � � � � Portanto, S = {–2, –2, –5}. O mesmo princípio é adotado em um sistema de equações lineares triangular superior (forma padrão obtida por meio do escalonamento). Nesse caso, usaremos como modelo um sistema de equações linea- res da forma UX = B, com • U � � � � � � � � � � � u � u u n nn 11 1 0 � � � � � • X x xn � � � � � � � � � � � 1 • B b bn � � � � � � � � � � � 1 Sistemas de equações lineares 89 Portanto, esse é um sistema triangular superior no qual a matriz dos coeficientes, U, tem seus elementos na forma uij = 0 para i > j. Denotamos u x u x u x b u x u x b u x b n n n n nn n n 11 1 12 2 1 1 22 2 2 2 � � � � � � � � � � � � � � � � � � � � � � �� Também podemos montar um algoritmo para a solução dos siste- mas no formato UX = B e, para isso, usaremos a i-ésima linha da forma: uii · xi + uii+1 · xi+1 + uii+2 · xi+2 + ... + uin · xn = bi Isolando xi, obtemos xi = bi – ui(i+1) · xi+1 – ui(i+2) · xi+2 – ... – uin · xn Portanto, podemos escrever esse raciocínio da seguinte maneira: Algoritmo 2 x b un n nn = Para i = (n – 1), (n – 2), ..., 1, faça: x b u x u u xi i j i n ij j ii ij j� � � � � � � � � � � �� �� � � 1 Exemρlo 5 Seja um sistema de equações lineares triangular superior da forma: 1 2 1 0 3 0 0 0 1 2 2 1 1 2 3 � � � � � � � � � � � � � � � � � � � � � � � �� � � � � � � � � � x x x m yd eg ag e/ Sh ut te rs to ck 90 Matemática para Computação Usando o Algoritmo 2, resolvemos esse sistema da seguinte forma: x b u3 3 33 1 1 1= = = x b u x u2 2 23 3 22 2 0 1 3 2 3 � � � � � � � � � x b u x u x u1 1 12 2 13 3 11 2 2 2 3 1 1 1 13 3 � � � � � � �� � �� � � � � � � � � � � Logo, a solução para esse sistema de equações é S � � ��� � � � � 13 3 2 3 1, , . Devemos notar que os algoritmos não dependem de linguagem de programação previamente escolhida e precisam ser adaptados à lin- guagem que queremos programar. 4.2.1 Classificação de um sistema de equações lineares Começaremos esse tópico elencando três exemplos simples (Figura 1) que serão resolvidos de forma escalonada e usados para exemplificar os tipos de soluções possíveis em um sistema de equa- ções lineares. Vamos utilizar uma calculadora on-line para resolver o escalonamento . Figura 1 Sistemas de equações escalonados por meio de calculadora on-line Sistema Escalonamento por meio de calculadora on-line x x x x 1 2 1 2 2 3 2 3 � � � � � � � �� � � � �� � � �� 1 1 3 2 2 3 1 1 2 0 1 3� � � � �� � � ��· (–3) L2 – 3 · L1 → L2 x x x x 1 2 1 2 2 3 3 6 9 � � � � � � � �� 1 2 3 6 3 9 � � �� � � �� � 1 2 3 0 0 0 � � �� � � ��· (–3) L2 – 3 · L1 → L2 x x x x 1 2 1 2 2 3 3 6 3 � � � � � � � �� 1 2 3 6 3 3 � � �� � � �� � · (–3) L2 – 3 · L1 → L2 1 2 3 0 0 6� � � �� � � �� Fonte: Elaborada pela autora. https://matrixcalc.org/pt/slu.html Sistemas de equações lineares 91 Mediante o processo de escalonamento da matriz ampliada, o siste- ma de equações lineares pode ser resolvido por meio de substituições regressivas. Ao observarmos o primeiro sistema de equações da Figura 1, temos que, se as matrizes ampliadas são equivalentes, a solução do sistema gerado pela matriz escalonada é equivalente à solução do sistema ori- ginal. Assim, podemos escrever: x x x 1 2 2 2 3 � � � � � � � � �� Logo, x2 = 3 e x1 = –1. Observando graficamente 1 essas duas retas que formam o nosso sistema de equações lineares, obtemos: Figura 2 Sistema de equações x x x 1 2 2 2 3 � � � � � � � � eq1: x + y = 2 eq2: –y = –3 y 9 8 7 6 5 4 3 2 1 1–1–2–3–4–5–6–7–8–9–10–11–12 2 3 4 5 6 7 8 90 –1 x A = (–1, 3) Fonte: Elaborada pela autora. Observamos que as retas formadas pela eq1 e eq2 se interceptam em um ponto que, não por acaso, é a solução do sistema. Ou seja, a so- lução de um sistema de equações é justamente o ponto de intersecção das retas que formam esse sistema. Entretanto, o que ocorre nos siste- mas de equações seguintes? No segundo sistema de equações da Figura 1, após o escalonamen- to, podemos escrever o sistema de equações equivalente da seguinte maneira: x x x x1 2 1 2 2 3 0 0 2 3 � � � � � � Para obter esse gráfico, utilizamos o software GeoGebra on-line. Disponível em: https://www. geogebra.org/graphing/jxrjp8dc. Acesso em: 15 jul. 2021. 1 https://www.geogebra.org/graphing/jxrjp8dchttps://www.geogebra.org/graphing/jxrjp8dc 92 Matemática para Computação Observe o gráfico a seguir formado pelas retas. Figura 3 Sistema de equações x x x x 1 2 1 2 2 3 3 6 9 � � � � � � � eq1: x + 2y = 3 eq2: 3x + 6y = 9eq2: 3x + 6y = 9 y 2 2 4 44 6 6 8 8 10 10 12 12–2 –2 –4–6–8–10–12–14–16–18 0 x Fonte: Elaborada pela autora. Observamos que eq1 e eq2, presentes na Figura 3, se sobrepõem, isto é, são retas coincidentes. Portanto, nesse caso, afirmamos que temos infinitos pontos de intersecção, o que nos permite concluir que temos infinitas soluções para o sistema de equações. Vamos fazer o mesmo com o terceiro sistema de equações da Fi- gura 1. Primeiro, reescreveremos o sistema de equações equivalente escalonado da seguinte forma: x x x x 1 2 1 2 2 3 0 0 6 � � � � � O qual representamos graficamente como: Figura 4 Sistema de equações x x x x 1 2 1 2 2 3 3 6 3 � � � � � � � eq1: x + 2y = 3 eq2: 3x + 6y = 3eq2: 3x + 6y = 3 y 2 2 4 44 6 6 8 8 10 10 12 12–2 –2 –4–6–8–10–12–14–16–18 0 x Fonte: Elaborada pela autora. Cr ea te d by G eo Ge br a Cr ea te d by G eo Ge br a. Sistemas de equações lineares 93 Já no sistema de equações x x x x 1 2 1 2 2 3 3 6 3 � � � � � � � �� , as equações eq1 e eq2 são paralelas, o que nos mostra que não têm pontos de intersecção. Isso significa que o último sistema de equações representado na Figura 1 não tem solução. Assim, podemos afirmar que existem três tipos de soluções possí- veis para um sistema de equações lineares: I. quando existe uma única solução, denomina-se sistema compatível e determinado; II. quando existem infinitas soluções, denomina-se sistema compatível e indeterminado; III. quando não existe solução, denomina-se sistema incompatível. Desejamos criar uma generalização para esse conceito para que possamos classificar um sistema de equações com base em sua matriz dos coeficientes e em sua matriz ampliada escalonada. Desse modo, introduziremos o conceito de posto de uma matriz. Definição 4 O posto p de uma matriz A é o número máximo de linhas não nulas após o seu escalonamento. Denotamos o posto da matriz dos coeficientes por pc e o posto da matriz ampliada por pa. Assim, seja um sistema de equações da forma: a x a x b a x a x b n n m mn n m 11 1 1 1 1 1 � � � � � � � � � � � � � � � � Com matriz dos coeficientes a a a a n m mn 11 1 1 � � � � � � � � � � � � � � � e matriz ampliada dada por a a b a a b n m mn m 11 1 1 1 � � � � � � � � � � � � � � � � .� Classificamos: I. Se pc = pa, o sistema é compatível. a. Se pc = pa = n, em que n é o número de variáveis do sistema, o sistema é compatível e determinado (solução única). b. Se pc = pa < n, o sistema é compatível e indeterminado (infinitas soluções). II. Se pc < pa, o sistema é incompatível. O material da aula Sistemas de equações lineares e ma- trizes, do professor Daniel Norberto Kozakevich, traz, além da teoria relacionada à classificação dos sistemas de equações lineares, muitos exemplos resolvi- dos. Sugerimos que eles sejam refeitos para fixar o conteúdo aprendido nesta subseção. Disponível em: http://www.mtm.ufsc. br/~daniel/7105/aula_3.pdf. Acesso em: 15 jun. 2021. Saiba mais http://www.mtm.ufsc.br/~daniel/fotos.htm http://www.mtm.ufsc.br/~daniel/7105/aula_3.pdf http://www.mtm.ufsc.br/~daniel/7105/aula_3.pdf 94 Matemática para Computação Reunimos no Quadro 1 os conceitos e as definições abordados até o momento. É importante notar que, para essa representação, escolhe- mos alguns sistemas de equações lineares como exemplo, para uma melhor compreensão dos resultados. Quadro 1 Síntese de conceitos Primeiro sistema Segundo sistema Terceiro sistema Sistema de equações x x x x 1 2 1 2 2 3 2 3 � � � � � � � �� x x x x 1 2 1 2 2 3 3 6 9 � � � � � � � �� x x x x 1 2 1 2 2 3 3 6 3 � � � � � � � �� Matriz dos coeficientes 1 1 3 2 1 1 0 1 � � � � � � � � � � � � � � 1 2 3 6 1 2 0 0 � � � � � � � � � � � � � 1 2 3 6 1 2 0 0 � � � � � � � � � � � � � pc pc = 2 pc = 1 pc = 1 Matriz ampliada 1 1 2 3 2 3 1 1 2 0 1 3 � � � � � � � � � � � � � � � 1 2 3 3 6 9 1 2 3 0 0 0 � � � � � � � � � � � � � 1 2 3 3 6 3 1 2 3 0 0 6 � � � � � � � � � � � � � � pa pa = 2 pa = 1 pa = 2 Posto pa = pc = n pa = pc < n pc < pa Denominação Compatível e determinado Compatível e indeterminado Incompatível Fonte: Elaborado pela autora. Percebemos que, por meio da análise da matriz dos coeficientes e da matriz ampliada, podemos classificar sistemas de equações de qual- quer tamanho, ou seja, formados por m equações e n variáveis. 4.3 Eliminação gaussiana Vídeo Agora, vamos resolver um sistema de equações lineares para que possamos, por intermédio desse desenvolvimento, definir o método da eliminação gaussiana usando, para isso, a fatoração matricial (decom- posição gaussiana). Desse modo, seja: 2 4 2 6 5 0 4 2 2 1 2 3 1 2 3 1 2 3 x x x x x x x x x � � � � � � � � � � � � � � Sistemas de equações lineares 95 Portanto, pela fatoração matricial, escrevemos A A M � � � � � � � � � � � � � � � 1 1 2 4 2 1 1 5 4 1 2 � ����� ����� multiplicandopor �� � � � � � � � � � � � � � � A M 2 2 2 4 2 0 3 6 0 7 2 � ����� ����� multiplicandopor �� � � � � � � � � � � � � � � A3 2 4 2 0 3 6 0 0 12 O que faz o M1? Zera todos os elementos abaixo da posição (1, 1). O que faz o M2? Zera todos os elementos abaixo da posição (2, 2). Com isso, ao invés de resolvermos A1 · x = b, resolvemos A3 · x = c, em que: A2 = M1 · A1 A3 = M2 · A2 = M2 · M1 · A1 e M2 · M1 · A1 · x = M2 · M1 · b = c Com base nesse exemplo, podemos definir: Definição 5 Uma matriz elementar triangular inferior de ordem n e índice k pode ser escrita como: M I men k T� � Em que e mi T � �0 , para i = 1, …, k e m m m mn � � � � � � � � � � � � � 1 2 ... é ortogonal a todos os vetores canônicos e1, e2, ..., ek. Então, 1 0 0 0 0 1 2 1... ... �� �� � � � � � � � � � � � � � � � � � m m m m n 0 1 0 0 0 1 2 2... ... �� �� � � � � � � � � � � � � � � � � � m m m m n 96 Matemática para Computação 0 1 0 0 1 2... ... posição�k n k m m m m � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� 0 Dessa forma, temos: M m m k n � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 1 1 1 0 0 0 0 1 ... ... . ... 11 0 1 1 1 0 posição�k ... ... ... � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 00 0 0 0 0 0 0 0 0 0 0 0 0 1 ... ...m m k n coluna�k � � � � � � � � � � � � � � � � � � � � � � � Logo, M m m k n � � � � � � � � � � � � � � � � � � � � 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 ... ... (1) é a matriz elementar triangular inferior de ordem n e índice k. Com a matriz elementar, podemos extrair os seguintes resultados: • Resultado 1: se M �I � �m �en k T� � � , então M �I � �m �en k T� � � �1 . • Resultado 2: dado x, com xk ≠ 0, existe uma única matriz elemen- tar triangular M, de índice k, que anula todos os elementos de x abaixo da posição k, mantendo todos os demais. De acordo com a fatoração gaussiana, se A é uma matriz com m linhas e n colunas, então temos m – 1 passos para obter a matriz A(m), tal que A(1) → A (2) = M1 · A (1) → ... → A(m) = Mm–1 · A (m–1) Sistemas de equações lineares 97 Assim, generalizando esse processo e escrevendo por meio de ma- trizes elementares, teremos A(k+1) = Mk · A (k) = Mk · Mk–1 · ... · M1 · A (1) em que M �I � �m �ek n k T� � � Logo, A I m e Ak n k k T k�� � � �� �� � �1 � ���� ���� Mk Que matricialmente é escrito como A A m m ak k k k m k kk k�� � � � � � �� � � � � � � � � � � � � � � � � � � � � � �1 1 0 0 0 0 , , ... aakn k� �� �� � �� Portanto, A A � m a k k k k k k kk k �� � � � �� �� � � � � � � � � � � � � � � � 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 , , mm a x m a m a a k k kn k m k kk k m k kk k kn k � � � � � � � � � � � � � � � � � � � � � 1 0 0 0 0 , , , �� � � � � � � � � � � � � � � � � que apresenta o processo de atualização de A(k). A matriz A(k+1) pode ser obtida por intermédio da matriz A(k), basta alterarmos o canto inferior direito, isto é, a aij k ij k�� � � ��1 , i = 1, ..., k e j = 1, ..., n a aij k ij k�� � � �� �1 0 , i = k + 1, ..., m e j = 1, ..., k Logo, a a m a �i k m� j k n ij k ij k ik kj k�� � � � � �� � � � � � � 1 1 1 , ,..., ,..., 98 Matemática para Computação Esse processo nos permite escrever o algoritmo a seguir: Algoritmo 3 – Decomposição de Gauss da matriz A Seja A mxn∈ , m > 1, r = min{m – 1, n} akk k� � � 0 A a a a a a a a a a k m n k m � � � � � � � � � � � � � � � � � 11 1 12 1 1 1 1 1 1 1 22 2 2 2 2 2 � � � � � � � 22 2 1 2 n kk k km k kn k k mm m a a a � m m m a � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� � �� � � � � � � � � � � � � � � � � � � � � � � � � � � � 1 1� amn m Em que mk são as posições abaixo da diagonal que são zeradas. Assim, para k = 1, 2, ..., r podemos escrever: a m a a i k mik ik ik kk � � � �, ,...,1 a a m a i k m j k n ij ij ik kj� � � � � � � , ,..., ,..., 1 1 Observação: os elementos akk k� � são chamados de elementos pivôs. m yd eg ag e/ Sh ut te rs to ck Vamos acompanhar o próximo exemplo para compreender como utilizar o Algoritmo 3. Exemρlo 6 Seja A � � � � � � � � � � � � � � 2 4 2 1 1 5 4 1 2 , a decomposição de Gauss ocorrerá em r = min{2, 3} = 2 passos. Então, fazemos: • Passo 1: a11 ≠ 0 M1 1 0 0 1 2 1 0 4 2 0 1 � � � � � � � � � � � � � � � � � � � Sistemas de equações lineares 99 A M A2 1 1 1 0 0 1 2 1 0 4 2 0 1 2 4 2 1 1 5 4 1 2 � � � �� � � � � � � � � � � � � � � � � � � � � � � � � � � � �� � � � � � � � � � � � � � � � � � � � 2 4 2 0 3 6 0 7 2 • Passo 2: a22 ≠ 0 M2 1 0 0 0 1 0 0 7 3 1 � � � � � � � � � � � � � � � � A M A3 2 2 1 0 0 0 1 0 0 7 3 1 2 4 2 0 3 6 0 7 2 � � � �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� � � � � � � � � � � � � � � � 2 4 2 0 3 6 0 0 12 Se o Algoritmo 3 for aplicado, a matriz encontrada será: A 3 2 4 2 1 2 3 6 2 7 3 12 � � � � � � � � � � � � � � � � � � � � � � O método de eliminação de Gauss pode ser observado, na subseção a seguir, mediante o chamado pivoteamento completo ou pivoteamento parcial. 4.3.1 Pivoteamento completo Seja a matriz A(k) da forma A a a k kk k lk ck k � � � � � �� � � � � � � � � � � � � � � � � � � � � � � � � � � � , 100 Matemática para Computação Caso o pivô akk k� � � 0 e os demais a �� ��ak k k m k k � � � � � 1, ,, ..., forem diferentes de zero, então podemos realizar o chamado pivoteamento completo. Nesse caso, trocamos akk k� � por alk ck k , � � . Para isso, fazemos a troca en- tre as linhas kk e lk e as colunas kk e ck. A troca de linhas equivale a realizar uma pré-multiplicação da ma- triz, ou seja, I �A Ak lk k k , · � � � �� Já a troca entre as colunas kk por ck pode ser calculada por meio de uma pós-multiplicação calculada por A I Ak k ck k� � � ��· , Portanto, A(k+1) = Mk · (Pk · A (k) · Qk) (2) Vamos acompanhar o exemplo a seguir para compreendermos melhor. Exemρlo 7 Seja A � � � � � � � � � � � 1 2 3 4 5 6 7 8 9 , então P23 1 0 0 0 0 1 0 1 0 � � � � � � � � � � � . Assim, P A23 1 0 0 0 0 1 0 1 0 1 2 3 4 5 6 7 8 9 1 2 3 7 8 9 4 5 6 � � � � � � � � � � � � � � � � � � � � � � � � � �. �� � � � � � Considerando Q23 1 0 0 0 0 1 0 1 0 � � � � � � � � � � � , escrevemos AQ23 1 2 3 4 5 6 7 8 9 1 0 0 0 0 1 0 1 0 1 3 2 4 6 5 7 9 8 � � � � � � � � � � � � � � � � � � � � � � � � � �. �� � � � � � Sejam Qi, Pi e Mi as matrizes utilizadas até o passo k, a generalização desse processo, fazendo-se a decomposição de A, com i = 1, ..., k, será: A(k+1) = Mk · (Pk · ... · M2 · (P2 · M1 · (P1 · A (1) · Q1) · Q2) · ... · Qk) Sistemas de equações lineares 101 Agora, vamos considerar a matriz A = A(1) e efetuar todas as trocas de linhas e colunas que foram aplicadas ao longo do processo até o passo k, encontrando outra matriz A’: A’(1) = Pk · ... · P1 · A (1) · Q1 · ... · Qk Aplicando o processo de Gauss em A’ e considerando que A’(i) são as matrizes encontradas e M’i as matrizes elementares usadas, temos que: A’(k+1) = M’k · ... · M’1 · A’ (1) Algoritmo 4 – Decomposição de Gauss da matriz A com pivoteamento completo Para k = 1, 2, ..., r, queremos encontrar lk, ck ≥ k, tal que |alk,ck| = max {|aij|, i, j ≥ k}. Se alk,ck = 0, faça r = k – 1, para akj ↔ alk,j, j = k, ..., n aik ↔ ai,ck, i = 1, ..., m a m a a i k mik ik ik kk � � � �, ,...,1 a a m a i k m j k n ij ij ik kj� � � � � � . , ,..., ,..., 1 1 O processo para realizar o pivoteamento parcial é semelhante, po- rém a diferença é que podemos realizar apenas a troca de linha (ou coluna), se isso já for suficiente para obter o pivô desejado. 4.4 Condicionamento de sistemas lineares Vídeo Antes de tratarmos do condicionamento de sistemas de equações lineares, vamos relembrar rapidamente os conceitos de norma de ve- tores e matrizes. 4.4.1 Norma de vetores e matrizes A análise do condicionamento de uma matriz depende do conceito de norma de matriz, que, por sua vez, depende da norma de um vetor. Assim, temos algumas definições que antecedem a construção da aná- lise do condicionamento, como as elencadas a seguir. 102 Matemática para Computação Definição 6 Norma de vetor é uma função ‖ · ‖: ℝn → ℝ x ↦ ‖x‖ Satisfazendo: • ‖x‖ ≥ 0, ∀ x ∈ ℝn; • ‖x‖ = 0 ⇔ x = 0; • ‖α · x‖ = |α| · ‖x‖, α ∈ ℝ; • ‖x + y‖ ≤ ‖x‖ + ‖y‖. Algumas das normas mais utilizadas, de acordo com Campos Filho (2018), são: I. Norma da soma de magnitudes: x 1 1 � � � xi i n II. Norma euclidiana: x 2 2 1 � � �Xi i n III. Norma do máximo ou norma infinita: x max x i n i� � � � � �1 O conceito de norma está relacionado geometricamente ao concei- to de distância. Dessa maneira, é comum trabalharmos com a defini- ção de distância entre pontos ou mesmo entre vetores. Veremos na sequência mais algumas definições que trazem esses conceitos, para que possamos aplicá-los no conceito de norma e distância de matrizes. Definição 7 A distância entre dois pontos é dada pela expressão d(x, y) = ‖x – y‖ para qualquer norma. Sistemas de equações lineares 103 Após apresentarmos a distância entre vetores, podemos trazer a definição de convergência, que considera como base as definições 8 e 9, as quais usam como eixo central a definição 7. Definição 9 {x(k)} → x em relação à norma ‖ · ‖∞ ⇔ lim x x k i k i � � � � � , i = 1, 2, ..., n. Definição 8 {x(k)} → x em relação à norma ‖ · ‖, se para todo ε > 0 existe um N(ε), tal que ‖x(k) – x‖ < ε,∀ k ≥ N (ε). Concluímos que todas as normas vetoriais no ℝn são equivalentes à convergência, ou seja, se {x(k)} → x em relação a uma norma ‖ · ‖, então {x(k)} → x em relação a qualquer outra norma ‖ · ‖. Quando se trata de matrizes, as relações são semelhantes. Definição 10 A norma de uma matriz An é uma função ‖ · ‖: ℝnxn → ℝ A ↦ ‖A‖ que satisfaz: • ‖A‖ ≥ 0, ∀ A ∈ ℝnxn; • ‖A‖ = 0 ⇔ A = 0 matriz nula; • ‖α · A‖ = |α| · ‖A‖, α ∈ ℝ; • ‖A + B‖ ≤ ‖A‖ + ‖B‖. Podemos definir a distância entre matrizes, apesar de parecer um conceito bastante estranho, da seguinte maneira: d(A, B) = ‖A – B‖. Com isso, a norma de uma matriz é definida usando os conceitos vistos anteriormente para as normas vetoriais, sendo que algumas nor- mas matriciais costumam ser mais adotadas do que outras. Observe a definição a seguir sobre uma dessas normas. Definição 11 Se ‖ · ‖ é uma norma vetorial, então A max A x max a x i n ij jn � � �� � �� � � � � 1 1 1 é uma norma matricial, que se chama norma natural ou induzida. 104 Matemática para Computação Normas induzidas (naturais) têm diversas vantagens, como: • Seja x ≠ 0 e ‖ · ‖ uma norma natural ou induzida pela norma ve- torial, então ‖Ax‖ ≤ ‖A‖ · ‖x‖ • ‖l‖ = 1; • Raio espectral ρ(A) = max|λ|, em que λ é um autovalor de A. Algumas das normas mais utilizadas são: I. Norma 1: A max A x max a | x j n iji=1 n 1 1 1 1 1 � � � � � � �| II. Norma euclidiana: A max A x x2 2 1 2 � � � � � �( )A AT III. Norma do máximo ou norma infinita: � � �� � � � ����� ����� A max A x max a | x i n máximo�d ij j=1 n � � �� � �� � � � 1 1 | aa�soma�das�linhas Com o conhecimento de algumas propriedades das normas de ve- tores e de matrizes, podemos entrar no assunto condicionamento. 4.4.2 Número de condicionamento Considere o sistema � . 1 1 1 2 10 5 1 2� � � � � � � � � � � � � � � � � � � � � x x , cuja solução exata é xexato � � � � � � � 5 5 . Estamos fazendo uma pequena perturbação no sistema quando al- teramos os elementos da matriz dos coeficientes ou do vetor indepen- dente de maneira muito suave, ou seja, com uma pequena alteração. Para esse sistema, vamos perturbar o vetor de termos independentes b � � � � � � � � 10 5 , para b1 10 01 5 � � � � � � � � , . Sistemas de equações lineares 105 O sistema passa a ser 1 1 1 2 10 01 5 1 2� � � � � � � � � � � � � � � � � � � � � � x x , , cuja solução é x � � � � � � � 5 007 5 003 , , , sendo que x xexato≈ e o resíduo (r = Ax – b) é pequeno, pois 1 1 1 2 5 007 5 003 10 5� � � � � � � � � � � � � � � � � � � � � � , , Agora, seja o sistema de equações representado por 1 1 1 001 1 10 10 005 1 2, , � � � � � � � � � � � � � � � � � � � � x x , cuja solução exata também é xexato � � � � � � � 5 5 , ao perturbarmos o vetor de termos independentes b, transformando-o em b1 10 10 1 � � � � � � �, , encontramos: 1 1 1 001 1 10 10 1 1 2, , � � � � � � � � � � � � � � � � � � � � x x cuja solução é x � � � � � � � � 100 90 . Se olharmos apenas para o resíduo, ou seja, para r = Ax – b, temos que 1 1 1 001 1 100 90 10 10 1, , � � � � � � � � � � � � � � � � � � � � � � b Contudo, percebemos que a solução se apresentou muito diferente do que foi encontrado no primeiro sistema. Por isso, a pergunta que fazemos é: Por que uma perturbação de mesma ordem de grandeza interferiu tanto em uma resposta, mas não na outra? A resposta para esse problema está justamente no condicionamen- to da matriz ou, mais especificamente, no número que representa esse condicionamento. Vamos supor que x resolve exatamente A · x = b, e x resolve aproxi- madamente A · x = b, isto é, A · x ≈ b e r é o resíduo r = b – A · x . Então, x x x cond A r b � � � � � 106 Matemática para Computação Queremos analisar se ‖r‖ ≈ 0 implica ‖x – x ‖ ≈ 0. Para isso, assumi- mos que r = b – A · x . Assim, desenvolvemos r = Ax – A · x = A(x – x ) (x – x ) = A-1 · r Mas, ‖x – x ‖ = ‖A-1 · r‖ ≤ ‖A-1‖ · ‖r‖ Pois estamos considerando uma norma induzida. Portanto, x x x A r x � � ��1 Como 1 x A b ≤ , temos que: x x x A r A b � � � ��1 Definindo cond(A) = ‖A-1‖ · ‖A‖, obtemos: x x x cond A r b � � � � � ou ER cond A ERx Erro�relativo�em�x b Erro�relativo�e ��� �� ��� �� � � � � mm�b O erro relativo em b é considerado porque r b Ax b b� � � � . Com isso, mesmo que ‖r‖ ≈ 0, não implica x x� � 0 , a menos que cond(A) também seja pequeno (CHAPRA, 2016). Concluímos assim que, quanto maior é o cond(A), é mais provável que o sistema seja sensível às mudanças em dados iniciais. Além disso, definimos: Definição 12 O número de condicionamento de uma matriz não singular A é condp(A) = ‖A‖p · ‖A-1‖p em que p é a norma adotada. Observe que o número de condicionamento depende da norma escolhida. Sistemas de equações lineares 107 A seguir, listamos as propriedades, considerando apenas normas induzidas. I. cond(A) ≥ 1 cond(A) = ‖A‖ · ‖A-1‖ ≥ ‖A · A-1‖ = ‖ I ‖ = 1 II. Se D é uma matriz diagonal, então cond D d d ii ii � � � max min , indepen- dentemente da norma escolhida. Por exemplo, na norma infinita: D d d dnn � � � � � � � � � � � � � � � 11 22 ... , D d d dnn � � � � � � � � � � � � � � � � � � � � � � � � 1 11 22 1 1 1 ... D dii��max , D d dii ii � � �1 1 1 � max min cond D d d ii ii � � � max min III. cond(αA) = cond(A), ∀ α ∈ ℝ, α ≠ 0. Isso significa que, se uma ma- triz for multiplicada por um escalar, seu número de condição não mudará: cond A A A A A cond A� � � � � � � � � � � � � � � � �� �1 11 1 IV. cond(A) = cond(A-1). O exemplo a seguir nos ajudará a compreender algumas dessas propriedades. Exemρlo 8 Seja um sistema de equações Ax = b, no qual A � � � � � � � � � 0 992 0 873 0 481 0 421 , , , , , assumimos que A max A x max a x i n ij j n � � �� � �� � � � � 1 1 1 Lembre-se de que, para facilitar esses cálculos, é possível usar diversas fer- ramentas computacionais. Sugerimos a página do Matrixcalc para o cálculo da matriz inversa de A. Disponível em: https://matrixcalc. org/pt/#%7B%7B0%2e992, -0%2e873%7D,%7B0%2e481, -0%2e421%7D% 7D%5E%28-1%29. Acesso em: 16 jul. 2021. Já para aqueles que se interessam por programa- ção, enquadrando-se os que estão iniciando nessa área, sugerimos o Python. Nesse caso, recomenda- mos o código que consta no Exemplo 8, que calcula o condicionamento da matriz A para a norma 1, norma euclidiana e norma infinita. Código 1: import numpy as np A = np.array([[0.992, -0.873],[0.481,- 0.421]], dtype=’double’) print(np.linalg. cond(A,p=1)) print(np.linalg. cond(A,p=2)) print(np.linalg.con- d(A,p=np.inf)) Saiba mais https://matrixcalc.org/pt/#%7B%7B0%2e992,-0%2e873%7D,%7B0%2e481,-0%2e421%7D%7D%5E%28-1%29 https://matrixcalc.org/pt/#%7B%7B0%2e992,-0%2e873%7D,%7B0%2e481,-0%2e421%7D%7D%5E%28-1%29 https://matrixcalc.org/pt/#%7B%7B0%2e992,-0%2e873%7D,%7B0%2e481,-0%2e421%7D%7D%5E%28-1%29 https://matrixcalc.org/pt/#%7B%7B0%2e992,-0%2e873%7D,%7B0%2e481,-0%2e421%7D%7D%5E%28-1%29 https://matrixcalc.org/pt/#%7B%7B0%2e992,-0%2e873%7D,%7B0%2e481,-0%2e421%7D%7D%5E%28-1%29 108 Matemática para Computação Assim, temos que a norma infinita para A será ‖A‖∞ = max{(|0,992| + |-0,873|), (|0,481| + |-0,421|)} = 1,865 Como desejamos calcular o condicionamento de A, precisamos en- contrar a matriz A–1 e, na sequência, encontrar ‖A-1‖∞. Para isso, fazemos A� � � � � � � �1 421 000 2 281 873 000 2 281 481 000 2 281 992 000 2 281 . . . . . . . . �� � � � � � � � Logo, ‖A-1‖∞ = max . . . . , . . . � � � � � � � � � � 421 000 2 281 873 000 2 281 481 000 2 281 992 000 2..281 � � � � � � � � � �� � � � �� = 645,77 Com isso, o condicionamento de A será cond(A) = ‖A-1‖ · ‖A‖ = 1,865 · 645,77 = 1.204,36 Portanto, o condicionamento de uma matriz pode ser analisado para compreendermos o comportamento do sistema de equações a ser resolvido. Além disso, podemos usar o condicionamento para ana- lisar a matriz dos coeficientes e, com isso, escolher o método mais ade- quado para a resolução do sistema. 4.5 Métodos iterativos Vídeo Um método iterativo é aquele que usa informações de, no mínimo, um passo anterior para resolver o seguinte, sendo de grande impor- tância na solução de problemas que envolvem matrizes esparsas de grande porte no caso dos sistemas de equações. Uma matriz esparsa tem como característica um grande número de elementos iguais; em geral, esse elemento repetido é o elemento neutro. São também consideradas matrizes esparsas aquelas com ele- mentos faltantes. Isso é comum quando essa matriz foi alimentada, por exemplo, por uma pesquisa que possuía dados incompletos de seus participantes. Essas matrizes tambémsão comuns no estudo da teoria dos grafos e na resolução de equações diferenciais. A seguir, definimos o formato dos métodos iterativos. Sistemas de equações lineares 109 Definição 13 Seja A ∈ ℝn⨯n esparsa e de grande porte, tal que Ax = b, os métodos itera- tivos têm o formato geral: A = N – P (3) Assim, N · x – P · x = b N · x = P · x + b = b tal que N · x = b seja mais fácil de ser resolvido do que A · x = b. O processo iterativo é definido por N · x(k+1) = P · x(k) + b, k = 0, 1 (4) com x(0) dado. Portanto, x(k+1) = N–1 · P · x(k) + N–1 · b (5) Se a sequência gerada {x(k)} converge para x* quando k → ∞, então N · x* = P · x* + b converge para Ax* = b, isto é, x* é a solução do sistema. Partindo desse processo principal, temos uma questão importante que diferencia os métodos iterativos: a escolha da matriz N. Assim, os métodos que serão tratados na sequência se diferenciam justamente por essa matriz. Vamos entendê-los. 4.5.1 Método de Gauss-Jacobi Como comentamos anteriormente, a escolha de N define diferentes métodos iterativos. O primeiro método que estudaremos é conhecido como método de Gauss-Jacobi ou simplesmente método de Jacobi. 4.5.1.1 Escolha de N No método de Jacobi, a matriz N será uma matriz diagonal, ou seja, N a a ann � � � � � � � � � � � � � � � 11 22 0 0 0 0 0 0 ... ... ... ... ... ... ... O matemático alemão Carl Gustav Jakob Jacobi (1804 – 1851) deixou importantes contribuições nas mais diversas áreas da Matemática. Dentre elas, encontramos a matriz Jacobiana, impor- tante para a resolução de problemas de cálculo avançado. Também é ele quem referenciamos quando trabalhamos com o método para solução de sistemas de equações iterativo que assume a matriz N como uma ma- triz diagonal. Para saber mais sobre Jacobi e suas contribuições, sugerimos o material disponível no Instituto Superior Técnico. Disponível em: http://e-escola. tecnico.ulisboa.pt/personalidade/ jacobi-carl-gustav-jakob. Acesso em: 16 jul. 2021. Saiba mais http://e-escola.tecnico.ulisboa.pt/personalidade/jacobi-carl-gustav-jakob http://e-escola.tecnico.ulisboa.pt/personalidade/jacobi-carl-gustav-jakob http://e-escola.tecnico.ulisboa.pt/personalidade/jacobi-carl-gustav-jakob 110 Matemática para Computação Pela equação (3), temos: P N A a a a a a a n n n n � � � � � � � � � � � � � 0 0 0 12 1 21 2 1 2 ... ... ... ... ... ... ... �� � � � � � � � � � Portanto, fazendo N · x = P · x + b, obtemos a a a x x xnn 11 22 1 2 0 0 0 0 0 0 ... ... ... ... ... ... ... ... � � � � � � � � � � � � � � nn n n n a a a a a � � � � � � � � � � � � � � � � � � � � � 0 0 12 1 21 2 1 ... ... ... ... ... ... aa x x x b b bn n n2 1 2 1 2 0... . ... ... � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� � � � � � � � � � � � Se aii ≠ 0 para todo i, então x� � N �P �x� � N �b T c � � �� �1 1� �� �� � �� �� , o que nos leva à seguinte equação x = Tx + c (6) que tem como representação matricial: x x x a a a a a a a a n n n 1 2 12 11 1 11 21 22 2 0 0 ... ... ... � � � � � � � � � � � � � � � � � � � 222 1 2 1 0 ... ... ... ... ... . � � � � � � � � � � � � � � � � � � � � � � � � a a a a x n nn n nn xx x b a b a b a n n nn 2 1 11 2 22... ... � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� � � � � As equações de iteração são obtidas quando isolamos, em cada equação do sistema, uma variável de cada vez. Assim, x a b a x � a x x a b k k n n k k 1 1 11 1 12 2 1 2 1 22 2 1 1 �� � � � � � �� � � � � �� � � � � � � � ... aa x a x x a b a x a k n n k n k nn n n k 21 1 2 1 1 1 1 � � � � �� � � � � �� � � � � � � � � � ... ... nn n n kx �, � � � �� � � � � �1 1 Veremos a interpretação gráfica do método na Figura 5. Sistemas de equações lineares 111 4.5.1.2 Interpretação gráfica do método Para apresentarmos a interpretação gráfica, vamos assumir que o sistema de equações é composto por duas equações e duas incógnitas. Para esse tópico, assumiremos alguns valores específicos para o siste- ma de equações de modo que possamos garantir uma representação gráfica consistente. Assim, seja Ax = b dado por duas retas r1 e r2, tais que r �x y r x y 1 2 5 2 8 : : � � � � � � � �� , assumiremos que x 0 1 2 1 2 � � � � � � � � �, . O gráfico com a intersecção entre essas duas retas, também compreendida como a solução do sistema de equações, será: Figura 5 Representação do sistema r �x y r x y 1 2 5 2 8 : : � � � � � � � y –0,5–1,5–2,5–3,5–4,5–5,5 –1–2 –2 –1,5 –0,5 0,5 0,5 1,5 2,5 3,5 4,5 5,5 6,5 7,5 8,51 2 3 4 5 6 7 8 r1 : x + y = 5 r2 : x + 2y = 8 A = (2,3) x(0) x(1) 9 1 1,5 2 2,5 3 3,5 4 4,5 5 5,5 6 –1 –3–4–5–6 0 x G J H I Fonte: Elaborada pela autora. 112 Matemática para Computação Para verificar se o método converge para a solução do sistema, fazemos: x x x x k k k k 1 1 2 2 1 1 5 4 1 2 �� � � � �� � � � � � � � � � � � � Assumindo, assim, x 0 1 2 1 2 � � � � � � � � � � � � � � � A próxima etapa é calcular x(1). Portanto, x x 1 1 2 1 5 1 2 9 2 4 1 2 1 2 15 4 � � � � � � � � � � � � � � � � � � �� � � � Logo, x �x �*1 9 2 15 4 2 3 � � � � � � � � � � � � � � � � � � � � � � � Portanto, o método converge para a solução do sistema. 4.5.1.3 Convergência do método Quando citamos métodos numéricos iterativos, sempre menciona- mos a convergência do método. Para o método de Jacobi, seja qualquer x(0) inicial, ou seja, ponto de partida, a sequência {x(k)} ficará definida por x(k+1) = T · x(k) + c Portanto, {x(k)} converge para uma única solução x, tal que x = T · x + c ⇔ ρ(T) <1 ou ‖T‖ < 1 ⇒ {x(k)} → x em que Ax = b para qualquer x(0). Sistemas de equações lineares 113 De acordo com Dornelles Filho (2016, p. 67), que valida o trabalho de Burden e Faires (2015), “o primeiro critério é necessário e suficiente, porém computacionalmente trabalhoso de ser verificado. O segundo critério é suficiente, mas não necessário, porém mais facilmente verifi- cável”. Usando a norma infinita, temos: T a a a a a a a a a a n n n nn � � � � � � � 0 0 12 11 1 11 21 22 2 22 1 ... ... ... ... ... ... aa a T n nn 2 0 1 ... � � � � � � � � � � � � � � � � � � � � � � � � (max soma das linhas) Portanto, a a ij iij j i n � � � � 1 1, para todo i, tal que a a � �iii ij n � � � � � , j j i 1 o que equivale a afirmar que A é diagonalmente dominante. Algoritmo 5 – Gauss-Jacobi • Passo 1: entrada: A, b, �, N, x(0) • Passo 2: k = 0 • Passo 3: para i = 1, 2, ..., n x a b a x a xi k ii i ij j i j k ij j i+1 n j k�� � � � � � � � �� � � � � � � � �� � � � �� � �1 1 1 1 • Passo 4: se x x �i 1, ..., ni k i k�� � � �� � �1 � , ou k > N, então x = x(k+1). Se não, k = k + 1, voltar para passo 3. O exemplo a seguir faz uma aplicação do algoritmo do método de Jacobi. 114 Matemática para Computação Exemplo 9 Vamos organizar a primeira iteração que permite resolver pelo mé- todo de Jacobi o sistema de equações Ax = b, com A �x x x x �e�b� � � � � � � � � � � � � � � � � � � � � � � � � � � 10 2 1 0 5 2 1 2 20 20 20 20 1 2 3 , ��� � � � � � � � Calculando as matrizes P, N-1 e T, temos P � � � � � � � � � � � � � � � � 0 2 1 0 0 2 1 2 0 , N� � � � � � � � � � � � � � � � � � � � � � 1 1 10 0 0 0 1 5 0 0 0 1 20 e �T � � � � � � � � � � � � � � � � � � � � � 0 1 5 1 10 0 0 2 5 1 20 1 10 0 . Podemos notar que a matriz A � � � � � � � � � � � � � 10 2 1 0 5 2 1 2 20 é diagonalmente dominante, pois ‖T‖ < 1. Consideraremos x 0 0 0 0 � � � � � � � � � � � � � . Assim, x b x x x b x x k k k k k k 1 1 1 2 3 2 1 2 1 3 1 10 2 1 5 0 2 �� � � � � � �� � � � � � � �� � � � � � � � �� �� �� � � � � � � � � � � � � � � �� � � � � �x b x x k k k 3 1 3 1 2 1 20 2 A ordem de convergência e a taxa de convergência também podem ser avaliadas. Lembrando que esses valores são descritos por inter- médio da análise da aproximação da solução numérica em relação à solução exata por meio da expressão lim x x C k k p Ordem�de�convergência Taxa�de�conv � �� � � � � � 1 x xk( ) eergência Sistemas de equações lineares 115 Desse modo, teremos p = 1. Temos, portanto, uma convergência linear e lim x x x x T k k k p� �� � � � � � � � 1 , pois x � �x T x ��xk k�� � � �� � � �� �1 Sendo assim, lim x x x x T k k k� �� � � � � � � � 1 1 Desse modo, além de conseguirmos resolver um sistema de equações por métodos chamados de iterativos, é possível avaliarmos a convergência do método, fato esse que é imprescindível para uma boa análise numérica sobre a aplicação de qualquer tipo de método numérico. 4.5.2 Método de Gauss-Seidel Assim como no método de Jacobi, a escolha da matriz N define os passos a seguir. Portanto, para definirmos o método de Gauss-Seidel, em primeiro lugar tratamos da matriz N. 4.5.2.1 Escolha de N No método iterativo de Gauss-Seidel, a escolha da matriz N se dá por uma matriz triangular inferior na forma N a a a a a an n nn � � � � � � � � � � � � � � � 11 21 22 1 2 0 0 0 ... ... ... ... ... ... ... Com isso, teremos P N A a a a n n� � � � � � � � � � � � � � � � � � � 0 0 0 0 0 0 12 1 2 ... ... ... ... ... ... ... �� 116 Matemática para Computação Portanto, assumindo N · x = P · x + b, obtemos a a a a a a x n n nn 11 21 22 1 2 10 0 0 ... ... ... ... ... ... ... � � � � � � � � � � � � � � xx x a a a n n n2 12 1 2 0 0 0 0 0 ... ... ... ... ... ... ... � � � � � � � � � � � � � � � � � � .... . ... ... 0 1 2 1 2 � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � x x x b b bn n �� � � � � � � � � E podemos escrever x a b a x a x x a b a k k n n k k 1 1 11 1 12 2 1 2 1 22 2 1 1 �� � � � � � �� � � � � �� � � � � � � � ... 221 1 1 2 1 1 1 11 x a x x a b a x k n n k n k nn n n k �� � � � �� � �� � � �� � � � � � � � � ... . ... ,� � � � � � �� � �� �a xn n n k 1 1 1 Note que, x k1 1�� � é calculado apenas com termos no passo x(k). Os demais valores para xi, com i = 2, …, n, além de utilizarem valores no passo k, também usam valores no passo k + 1 para os xi elementos, com xi = 1, …, n – 1. 4.5.2.2 Interpretação gráfica do método Para apresentarmos a interpretação gráfica, adotaremos o mesmo princípio usado no método de Gauss-Jacobi e o mesmo sistema de equações lineares. Assim, seja Ax = b dado por duas retas r1 e r2, tais que r �x y r x y 1 2 5 2 8 : : � � � � � � � �� . Assumiremos x 0 1 2 1 2 � � � � � � � � �, . A seguir, apresentamos o gráfico que mostra a intersecção entre essas duas retas, também compreendida como a solução do sistema de equações. Sistemas de equações lineares 117 Figura 6 Sistema de equações r �x y r x y 1 2 5 2 8 : : � � � � � � � y –0,5–1,5–2,5–3,5–4,5–5,5 –1–2 –2 –3 –1,5 –2,5 –0,5 0,5 0,5 1,5 2,5 3,5 4,5 5,5 6,5 7,5 8,5 9,5 101 2 3 4 5 6 7 8 r1 : x + y = 5 r2 : x + 2y = 8 A = (2,3) x(0) x(1) 9 1 1,5 2 2,5 3 3,5 4 4,5 5 6 5,5 –1 –3–4–5–6 0 x G H JI Fonte: Elaborada pela autora. Para verificarmos se o método converge para a solução do sistema, fazemos: x x x x k k k k 1 1 2 2 1 1 1 5 4 1 2 �� � � � �� � �� � � � � � � � � � � Assumindo, então, x 0 1 2 1 2 � � � � � � � � � � � � � � � � � 118 Matemática para Computação A próxima etapa é calcular x(1). Portanto, x x 1 1 2 1 5 1 2 9 2 4 1 2 9 2 7 4 � � � � � � � � � � � � � � � � � � �� � � � Logo, x x*1 9 2 7 4 2 3 � � � � � � � � � � � � � � � � � � � � � � � � � Assim, o método converge para a solução do sistema. 4.5.2.3 Convergência do método De acordo com Chapra (2016), temos que as condições para a con- vergência do método coincidem com as condições já vistas no método de Jacobi, ou seja, ρ(T) ≤ 1, em que T = N-1 · P. Além da verificação por meio do raio espectral, podemos usar uma condição suficiente, conhecida por critério de Sassenfeld, como expressam Burden e Fraires (2015). De acordo com esses dois autores, precisamos calcular βj, com j = 1, 2, ..., n em que �1 12 13 1 11 1� � � � � a a a a n... � � � j j j j j j j jn jj a a a a a j n� � � � � � � � � � � � �1 1 1 1 1 1 2 ... ... , ,...,, , Se β = max1≤j≤n, βj < 1, então o método de Gauss-Seidel converge para x independente de x(0), isto é, {x(k)} → x. A ordem de convergência, assim como no método de Jacobi, é li- near, e a taxa de convergência será igual a β, sendo que, quanto menor seu valor, mais rápida será a convergência. O exemplo a seguir esclare- ce esses conceitos. Sistemas de equações lineares 119 Exemρlo 10 Seja A � � � � � � � � � � � 8 2 1 5 4 1 4 3 4 uma matriz não diagonalmente dominante, note que ρ(T) ≤ 1, pois os autovalores de T são λ1 = 0, λ2 = 0,2983 e λ3 = 0,2095. Portanto, podemos usar o critério de Sassenfeld. Assim, obtemos �1 2 1 8 1� � � � � 2 15 1 4 23 32 1� � � � � � � � 3 1 24 3 4 117 128 1� � � � � � Nesse caso, como βi < 1 para i = 1, 2, 3, podemos aplicar qualquer um dos métodos iterativos vistos anteriormente (Gauss-Jacobi ou Gauss-Seidel). O que podemos afirmar sobre a relação entre os critérios de linha e de Sassenfeld? Se o critério de linhas for satisfeito, então o critério de Sassenfeld tam- bém será. Se o critério de Sassenfeld não for satisfeito, o critério de linhas também não será. Resumidamente: CL⇒ CS e não CS ⇒ não CL Por intermédio da análise do critério de Sassenfeld para o método de Gauss-Seidel, notamos que o método gera uma sequência conver- gente. Assim, se ‖x(k+1) – x‖ ≤ β ‖x(k) – x‖, ∀ k 120 Matemática para Computação Então, lim k k k Ordem�de�convergência Taxa�de�co x x x x � �� � � � � � � � � � 1 1 ��� nnvergência Observação: a taxa de convergência é menor do que a taxa do mé- todo de Gauss-Jacobi, pois: a a a a a a a ak k k k k k kn kk k k k k1 1 1 1 1 1 1� � � � � � � � � � �� � � �� �... ... ..., , , ,, ... ,k kn kk a a �k� � � �1 a a a a a max a ak k k k k k kn kk k k k k1 1 1 1 1 1� � � � � � � � � �� � � �� �... ... ..., , , 11 1� � �� � � �� � � � �� � �� a a a T kk k kn kk , .... , βk < ‖T‖, ∀ k Então, maxβk < ‖T‖. Logo, � ��� ��� Taxa�de�Gauss Seidel Taxa�de�Gauss Jacobi T � � � Algoritmo 6 – Gauss-Seidel • Passo 1: entrada: A, b, �, N, x(0). • Passo 2: k = 0. • Passo 3: para i = 1, 2, ..., n x a b a x a xi k ii i ij j i j k ij j j k�� � � � �� � � � � �� � � � � � � � �� � � �� �1 1 1 1 1 1 i n ��� • Passo 4: se x x �para�i ni k i k�� � � �� � �1 1� , ,..., , ou k > N, então x = x(k+1). Se não, k = k + 1, voltar para o passo 3. Vamos acompanhar o exemplo a seguir, no qual utilizamos o algo- ritmo de Gauss-Seidel. Sistemas de equações lineares 121 Exemρlo 11 Seja a matriz A dada por A � � � � � � � � � � � � � 10 2 1 0 5 2 1 2 20 , resolva, utilizando o método de Gauss-Seidel, o sistema de equações dado por Ax � � � � � � � � � � � 20 20 20 , considerando x 0 0 0 0 � � � � � � � � � � � � � . Para isso, fazemos x x x x x x k k k k k 1 1 2 3 2 1 1 1 3 1 10 20 2 1 5 20 0 2 �� � � � � � �� � �� � � � �� � � � � � � � � � kk k k kx x x � � �� � �� � �� � � � � � � � � � � �� � � � � �3 1 1 1 2 11 20 20 2 Devemos notar que cada método se adapta melhor a um tipo de sis- tema ou situação aplicada. Os métodos podem ser comparados, com isso, geram uma análise mais profunda dos resultados obtidos. Compare os métodos e faça a análise dos resultados. Desafio CONSIDERAÇÕES FINAIS Com este capítulo foi possívelrevermos alguns conceitos estudados nos ensinos médio e fundamental, além de aprendermos algumas teorias ainda não trabalhadas nos ensinos de base. Temos com isso várias estratégias para a resolução de sistemas de equações lineares vinculados diretamente ao conceito de matrizes e transformados em algoritmos, para conseguirmos pensar em estratégias computacionais de programação para tais métodos. A intenção é munir você de ferramentas que serão extremamente úteis não só no que se refere à resolução de problemas, mas em muitas outras situações, de maneira teórica e aplicada. Também indicamos que você acesse aos links sugeridos como comple- mentação ao conteúdo e resolva o máximo de exercícios possíveis sobre o tema. Acreditamos que o tripé teoria, prática e aplicação é necessário para a boa compreensão de qualquer conceito. 122 Matemática para Computação ATIVIDADES Seja A a matriz dos coeficientes de um sistema de equações lineares do tipo Ax = b, por que precisamos ter det ≠ 0 para garantir a inversão dessa matriz? Explique. Atividade 1 Um sistema de equações lineares pode ter como solução infinitas solu- ções. Isso é válido para o sistema a seguir? Justifique. x y z x y z x y z � � � � � � � � � � � � � � � � 1 2 2 2 2 1 Atividade 2 Explique, com suas palavras, o que significa a análise de convergência de um método e qual é a sua importância para garantir o resultado encontrado. Atividade 3 REFERÊNCIAS BURDEN, R. L.; FAIRES, J. D. Análise numérica. São Paulo: Cengage Learning, 2015. CAMPOS FILHO, F. F. Algoritmos numéricos: uma abordagem numérica de cálculo numérico. Rio de Janeiro: LTC, 2018. CHAPRA, S. C.; CANALE, R. P. Métodos numéricos para engenharia. 7. ed. Porto Alegre: AMGH, 2016. DORNELLES FILHO, A. A. Fundamentos de cálculo numérico. São Paulo: Bookman, 2016. LEON, S. J. Álgebra linear com aplicações. 9. ed. Rio de Janeiro: Livros Técnicos e Científicos, 2019. Grafos e árvores 123 5 Grafos e árvores O primeiro teorema desenvolvido na teoria dos grafos é atribuído ao matemático Leonhard Euler. Isso ocorreu no ano de 1736. Euler desen- volveu um modelo que permitia encontrar um caminho passando pe- las sete pontes da cidade de Königsberg, antiga Prússia, hoje chamada Kaliningrado, na atual Rússia. Mas não era um caminho qualquer. Uma vez que se passasse por determinado trecho para chegar em uma das pontes, aquele caminho precisava ser retirado do modelo e, assim, não era possível passar duas vezes pelo mesmo trecho do caminho. Euler trabalhou sobre esse modelo assumindo algumas simplificações das ligações entre as regiões e desenvolveu um teorema que estabelece em que condições é possível percorrer cada trecho (linha) exatamente uma vez e voltar ao ponto inicial. Esse tipo de modelo, hoje em dia, é usado por empresas como Amazon, Uber e Correios, que dependem, por exemplo, de rapidez no transporte de mercadorias. Mas não é só o transporte de produtos que se beneficia desses conceitos. Facebook, Google e outras gigantes da tecnologia tam- bém usam a teoria dos grafos para o transporte de informações. Vamos ver, ao longo do texto, a teoria e as aplicações do conceito de grafos e a importância dessa grande área do conhecimento, que por si só renderia uma obra inteira. Com o estudo deste capítulo, você será capaz de: • conhecer um pouco a história dos grafos, suas terminologias e seus tipos; • vincular o conceito de grafos e árvores aos conceitos de funções; • aplicar a formulação matricial ou vetorial ao conceito de grafo por meio dos caminhos entre vértices e arestas; • compreender o conceito de árvore como subgrupo dos grafos; • identificar alguns algoritmos de busca representados por grafos ou árvores. Objetivos de aprendizagem 5.1 O que é um grafo: terminologia e tipos Vídeo A teoria dos grafos, que teve início com um modelo desenvolvido por Euler em 1736, é hoje a base de diversas estruturas matemáticas e computacionais, como as redes neurais, a criação de fluxogramas, as redes de comunicação, os modelos de fluxo de dados, os algoritmos de escalonamento e de pesquisa e ordenação, o layout de circuitos e os modelos de máquinas de estado. Ha ha m h an uk a~ co m m on sw ik i/W ik im ed ia C om m on s Leonhard Paul Euler é um dos grandes nomes da matemática e da física, mas acabou exercendo influência em muitas outras áreas, inclusive na mú- sica. Nascido na Basileia, Suíça, em 1707, passou a maior parte de sua vida na Rússia e na Alemanha e faleceu em São Petersburgo, Rússia, em 1783. O problema modelado por Euler é conhecido como o problema das sete pontes de Königsberg e con- siste em um algoritmo que permite passar pelas sete pontes dessa cidade, hoje chamada Kaliningrado, na Rússia, sem passar pelos caminhos já percorridos. Na sequência de figuras a seguir, é possível acom- panhar o modelo usado nessa construção. A Figura 1 mostra um pedaço do Rio Prególia, onde ao fundo conseguimos observar uma das pon- tes. Na época de Euler, as duas grandes ilhas localiza- das nessa extensão do rio formavam um importante complexo interligado por 7 pontes. 124 Matemática para ComputaçãoMatemática para Computação Figura 1 Modelo real Gumerov Ildar/Wikimedia Commons Grafos e árvores 125 A Figura 2 foi idealizada para a comemoração dos 600 anos da fa- mília real. Seu desenho está embasado em uma gravura de Joachim Bering (1613) e data de aproximadamente 1813. Figura 2 Modelo físico M er ia n- Er be n/ W ik im ed ia C om m on s A imagem original não apresenta as marcações destacadas sobre as pontes e sobre o Rio Prególia. Por fim, a Figura 3 apresenta o modelo matemático proposto por Euler, que permitia a conexão entre as diferentes regiões do complexo formado pelo rio, as ilhas e as sete pontes. Figura 3 Modelo matemático Nu x/ W ik im ed ia C om m on s 126 Matemática para Computação Esse modelo foi idealizado em 1736, portanto, muitas mudanças ocorreram ao longo dos anos, sendo que uma delas foi a derrubada de algumas das pontes. A Figura 4, a seguir, apresenta a vista por satélite da cidade de Kaliningrado no ano de 2021. Figura 4 Visualização de Kaliningrado por satélite Fonte: Google Earth, 2021. A teoria dos grafos é bastante extensa e precisaríamos de pelo menos uma obra inteira para discutirmos sobre ela em todos os seus detalhes. Mas traremos as características mais importantes quando pensamos em possibilidades de transcrição de grafos e árvores para algoritmos, vincu- lando esses conceitos às funções, aos vetores e às matrizes. A estrutura de um grafo está diretamente relacionada às funções e às matrizes. De maneira não formal, podemos afirmar que um grafo é um par (ou um trio) de conjuntos. Formalmente temos a seguinte definição: Definição 1 Um grafo é um objeto matemático (ou uma estrutura matemática) formado por dois conjuntos. O primeiro deles, que denotaremos por V, é o conjunto de vérti- ces. O segundo é o conjunto que relaciona os vértices (BOAVENTURA NETTO; JURKIEWICZ, 2017). Grafos e árvores 127 As relações entre vértices são chamadas de arestas. Portanto, o se- gundo conjunto, denotado por A, é o conjunto de arestas. Assim, o gra- fo é denotado por G = (V, A). Por sua vez, o conjunto de arestas A, que relaciona dois vértices – v e w –, tem elementos denotados por (v, w), sendo que v, w ∈ V. Com isso, temos que os elementos do conjunto de arestas são pares ordenados. Alguns autores referem-se aos vértices como nós. Portanto, qual- quer uma das nomenclaturas pode ser usada de acordo com a aplica- ção e a área em que o grafo está inserido. Exemρlo 1 Determine os conjuntos de vértices e arestas do grafo representa- do na Figura 5. Figura 5 Grafo com quatro nós e cinco arestas Fonte: Elaborada pela autora. 1 4 2 3 Observando a figura, identificamos os quatro vértices (nós) demar- cados com a numeração de 1 a 4. Além disso, conseguimos descrever as arestas que interligam alguns desses nós. Usando a notação defini-da anteriormente, escrevemos: • G = (V, A) • V = {1, 2, 3, 4} • A = {(1, 2), (1, 3), (2, 3), (2, 4), (3, 4)} 128 Matemática para Computação O número de vértices é representado por n = |V|. Logo, para o Exemplo 1, temos n = 4. Já o número de arestas é representado por a = |A|, observe que no grafo da Figura 5 temos a = 5. Esse é um exemplo de grafo não orientado (não dirigido, não di- recionado). Essa estrutura matemática pode ser vista em muitas si- tuações aplicadas. Um circuito eletrônico é formado por componentes e placas, mas, em geral, o que desejamos saber é o caminho percorrido pela corrente elétrica que passa por esses componentes. Sistemas eletrônicos ou sistemas digitais funcionam por meio da abertura e do fechamento de chaves lógicas (portas lógicas), sendo que o fechamento permite que a energia passe pelo sistema, e a abertura faz com que a energia seja cortada. Essas duas variáveis são represen- tadas matematicamente por 0 e 1, o que é conhecido como sistema binário (ou base binária). As portas lógicas são formadas com base em transistores, mosfets e resistores e cada uma realizará uma operação lógica diferente, tendo também uma simbologia padrão relacionada. As Figuras 6 e 7 mostram um pouco dessa simbologia. Figura 6 Porta lógica AND Fonte: Elaborada pela autora. A B Xe Figura 7 Porta lógica OR Fonte: Elaborada pela autora. A B Xou A junção de diferentes portas lógicas está representada na Figura 8. Figura 8 Portas lógicas Fonte: Elaborada pela autora. A B C X e You Para saber mais sobre circuitos e sistemas eletrônicos, indicamos as seguintes leituras: Organização estrutura- da de computador, que esclarece essa teoria com o auxílio de imagens e re- sume algumas seções da obra Organização Estrutu- rada de Computadores de Andrew S. Tanenbaum. Disponível em: http://www.dpi. inpe.br/~carlos/Academicos/ Cursos/ArqComp/aula_5bn1.html. Acesso em: 24 ago. 2021. Na Apostila de teoria para circuitos digitais, escrita por Alexandre Santos de la Vega, você saberá mais sobre a teoria para circuitos eletrônicos Disponível em: http://www. telecom.uff.br/~delavega/public/ CircDig/apostila_teo_cd.pdf. Acesso em: 24 ago. 2021. Leitura http://www.dpi.inpe.br/~carlos/Academicos/Cursos/ArqComp/aula_5bn1.html http://www.dpi.inpe.br/~carlos/Academicos/Cursos/ArqComp/aula_5bn1.html http://www.dpi.inpe.br/~carlos/Academicos/Cursos/ArqComp/aula_5bn1.html http://www.telecom.uff.br/~delavega/public/CircDig/apostila_teo_cd.pdf http://www.telecom.uff.br/~delavega/public/CircDig/apostila_teo_cd.pdf http://www.telecom.uff.br/~delavega/public/CircDig/apostila_teo_cd.pdf Grafos e árvores 129 Apesar de esse tipo de sistema parecer bastante complexo, pode- mos simplificá-lo usando vértices e arestas, já que o que desejamos entender é o percurso realizado pela corrente elétrica. Figura 9 Circuito eletrônico x grafo Esquema 1 3 Grafo 5 42 3 5 42 1 Fonte: Adaptado de Goldbarg; Goldbarg, 2012. Quando conhecemos a direção das arestas, ou seja, o caminho impos- to entre um vértice e outro, temos um vetor que nos orienta sobre qual é o vértice de partida e qual é o vértice de chegada. Nesse caso, o grafo formado por esses vértices e essas arestas é chamado de grafo dirigido (ou digrafo). As Figuras 10 e 11, a seguir, mostram exemplos de grafos digrafos. Figura 10 Grafo dirigido com quatro nós e cinco arestas Figura 11 Digrafo composto por 20 nós e 20 arestas Fonte: Elaborada pela autora. 1 4 2 3 al ri/ Sh ut te rs to ck Note que, no grafo da Figura 10, temos os mesmos vértices do grafo da Figura 5, porém agora as arestas estão orientadas. Dessa maneira, escrevemos o conjunto de arestas como: A = {(1, 2), (2, 3), (3, 2), (4, 2), (3, 1), (4, 3)} Podemos associar a cada aresta uma função. Nesse caso, teremos uma tripla ordenada da forma G = (V, A, f), em que f é uma função, O material Uma introdução sucinta à teoria dos grafos, dos professores Feofiloff, Kohayakawa e Wakabayashi, apresenta de maneira bas- tante didática e acessível a estrutura conceitual e alguns exemplos sobre a teoria dos grafos. É um material bem completo que pode ser usado como complemento de nosso material. Disponível em: https://www.ime. usp.br/~pf/teoriadosgrafos/texto/ TeoriaDosGrafos.pdf. Acesso em: 24 ago. 2021. Leitura https://www.ime.usp.br/~pf/teoriadosgrafos/texto/TeoriaDosGrafos.pdf https://www.ime.usp.br/~pf/teoriadosgrafos/texto/TeoriaDosGrafos.pdf https://www.ime.usp.br/~pf/teoriadosgrafos/texto/TeoriaDosGrafos.pdf 130 Matemática para Computação f: A → P (V), que associa a cada aresta um subconjunto de dois ou de um elemento de V, interpretado como os pontos terminais da aresta. Em um grafo ou digrafo com pesos, uma função adicional A → ℝ associa um valor a cada aresta, o que pode ser considerado como seu “custo”. O exemplo a seguir esclarece esses conceitos. Exemρlo 2 Considere o grafo representado na Figura 12 a seguir. Determine o número e o conjunto de vértices e arestas desse grafo. Figura 12 Grafo com custos nas arestas al ri/ Sh ut te rs to ck Note que esse grafo apresenta valores em suas arestas, portanto, identificamos que esses valores podem ser descritos por uma função custo, como definido anteriormente. Na sequência, apresentamos o conjunto de vértices, sendo n o nú- mero de elementos desse conjunto, e, então, o número de vértices. • V = {A, B, C, D, E, F} • n = 6 Após essa etapa, montamos o conjunto de arestas, que leva em consideração o sentido de cada uma delas. O valor a = 9 representa o número de elementos desse conjunto, logo, é o número de arestas. A = {(A, B), (A, D), (B, C), (B, E), (C, E), (C, F), (D, C), (D, E), (E, F)} Podemos analisar a adjacência entre vértices por meio da conexão entre arestas. A definição para esse conceito é apresentada a seguir. Existem diversos tipos de grafos: completos, regulares, nulos, entre outros. Para saber mais sobre esse assunto e poder escolher qual o melhor tipo de grafo para determinada representa- ção, sugerimos o material Grafos e algoritmos, de Filipe Chagas. Disponível em: https://medium. com/@filipe.chagas/os-grafos- e-os-algoritmos-697c1fd4a416. Acesso em: 24 ago. 2021. Saiba mais https://medium.com/@filipe.chagas/os-grafos-e-os-algoritmos-697c1fd4a416 https://medium.com/@filipe.chagas/os-grafos-e-os-algoritmos-697c1fd4a416 https://medium.com/@filipe.chagas/os-grafos-e-os-algoritmos-697c1fd4a416 Grafos e árvores 131 Definição 2 Se um vértice v do grafo G é um dos extremos de alguma aresta a desse grafo, então, a incide em v e vice-versa. Dois vértices v e w de um grafo G são adjacen- tes (ou vizinhos) se existir uma aresta de G cujos extremos são v e w. Observe a Figura 13 para compreender a definição anterior. A ares- ta a4 incide sobre os vértices v1 e v3, logo, v1 e v3 são adjacentes. Figura 13 Grafo G Fonte: Elaborada pela autora. v1 v3 v4 a4 a1 a2 a3 a5 v2 Portanto, a estrutura dos grafos é construída com base em modelos matemáticos que transmitirão um resultado aproximado (ou exato) a problemas físicos. 5.1.1 Caminhos, passeios e trilhas Agora, vamos retomar a Figura 13 para tratar do conceito de caminho. Ou seja, as arestas serão interpretadas como estruturas que determinam caminhos. Um caminho do vértice v1 para o vértice v4, no grafo G, é uma se- quência de vértices v1, v2, v3, v4, de tal modo que (v1, v2), (v2, v3), (v3, v4) são arestas em A. O comprimento (ou tamanho) de um caminho é o número de arestas que ele contém. Um caminho simples é um caminho em que todos os vértices são diferentes, com a possível exceção do primeiro e do último. Um ciclo é um caminho simples em que o primeiro e o último vértices são iguais. Um ciclo também pode ser chamado de caminho fechado. Um trajeto é um caminho no qual todas as arestas são distintas. 132 Matemática para Computação De acordo com Nicoletti e Hruschka Júnior (2018), quando nenhuma aresta aparece mais do que uma vez, tendo em umgrafo os vértices u e v, sendo u o vértice inicial e v o vértice final, chamamos de trilha. Se u ≠ v, teremos uma trilha aberta. Caso u = v, obtemos uma trilha fechada ou circuito. Ainda por Nicoletti e Hruschka Júnior (2018, p. 78), temos que (1) Uma trilha é um passeio no qual nenhuma aresta é repetida. (2) Um caminho é um passeio no qual nenhum vértice é repe- tido. (3) Consequentemente, em um caminho nenhuma aresta pode ser repetida, o que garante que todo caminho é uma trilha. (4) Nem sempre toda trilha é um caminho. (5) Por definição, todo caminho é um passeio. Afirmamos que uma estrutura matemática é um grafo conexo (ou interligado) se existir pelo menos um caminho entre cada par de vérti- ces do grafo. Caso contrário, o grafo é chamado de desconexo. Toda essa estrutura matemática pode ser usada em diversas situa- ções aplicadas. Por exemplo, uma pequena empresa de entrega de re- feições pode usar um modelo de grafo para resolver o problema da entrega de refeições quentes, em um intervalo de tempo de duas horas e com o menor custo possível para a empresa, ou seja, minimizando o trajeto para as entregas. Esse tipo de modelo, que não é dos mais simples, mas que pode ser idealizado por meio dos conceitos aprendidos neste capítulo, precisa ser resolvido em tempo real. É nesse momento que entra a computação científica. Assim, o grafo precisa ser escrito em um formato em que o computador possa lê-lo e operá-lo. Para essa transcrição, serão necessários conceitos como funções, matrizes e vetores, que viabilizarão o cálculo de problemas logísticos como o citado anteriormente. 5.2 Representação computacional de um grafo Vídeo Visualmente os grafos são estruturas bem fáceis de serem com- preendidas, mas quando precisamos levar essas informações para a área computacional, a representação gráfica pode ser um complicador. Assim, foram desenvolvidas formas de representar os grafos por meio de matrizes e sequências, fazendo com que a estrutura do grafo possa ser representada computacionalmente de maneira simples. Para conhecer um pouco mais sobre grafos conexos e desconexos e visualizar exemplos desses casos, indicamos o material Conceito básico da teoria de grafos. Disponível em: https://www.inf. ufsc.br/grafos/definicoes/definicao. html. Acesso em: 24 ago. 2021. Saiba mais https://www.inf.ufsc.br/grafos/definicoes/definicao.html https://www.inf.ufsc.br/grafos/definicoes/definicao.html https://www.inf.ufsc.br/grafos/definicoes/definicao.html Grafos e árvores 133 O problema das sete pontes de Königsberg tem seu grafo descrito na Figura 14 a seguir. A 1 2 3 4 6 7 5 B C D Figura 14 As setes pontes de Königsberg Fonte: Elaborada pela autora. Note que os vértices A, B e D têm três arestas, enquanto C tem cin- co. O número de arestas que incide sobre cada vértice determina o grau de um vértice. Logo, podemos afirmar que C tem grau cinco, en- quanto A, B e D têm grau três. O grau de um grafo é a soma dos graus de seus vértices. O teorema do aperto de mãos (handshaking) ainda permite que escrevamos que o grau de um grafo G é igual a duas vezes o número de arestas de G. Euler provou que se um vértice tem um número ímpar de arestas, então, caso queira percorrer as arestas apenas uma vez, nunca acaba- rá no vértice que começou (GOLDBARG; GOLDBARG, 2012; NICOLETTI; HRUSCHKA JÚNIOR, 2018). Esse grafo pode ser representado por uma matriz chamada matriz de adjacência, que será escrita como a seguir. 0 0 1 1 0 1 1 0 1 1 1 0 1 1 1 0 � � � � �� � � � � � � � A B C D A B C D Veremos como construir esse tipo de matriz. O teorema de handsha- king (aperto de mãos) é descrito para grafos não direcionados e finitos, compostos por um núme- ro par de vértices de grau ímpar. A analogia ao aperto de mãos se faz, pois, supondo que exista um grupo de pessoas em que algumas apertam mãos, um núme- ro par de pessoas deve ter apertado um número ímpar de mãos de outras pessoas. Isso também nos permite afirmar que a soma dos graus de todos os vértices de um grafo não direcionado finito é duas vezes o número de arestas desse grafo. Em circuitos digitais o handshaking é definido como o processo de troca de sinais pelo qual dois dispositivos digitais ou sistemas estabelecem entre si uma comunicação (FLOYD, 2007). Saiba mais 134 Matemática para Computação 5.2.1 Representação por meio de matrizes de adjacências Dado um grafo G com n vértices, podemos representá-lo em uma matriz que está em um espaço de tamanho |V| ⨯ |V|. Portanto, po- demos chamá-la de B (ordem n) com |V| = n. Essa é uma matriz de G (grafo G(V, A)), logo, denotamos Bn⨯n (G), em que os elementos de Bn⨯n (G) serão [bij]. Os elementos bij guardam informações sobre como os vértices adja- centes se relacionam na forma: B i j se i j caso contrário ( , ) , , , � � ����� �� 1 0 A Se as arestas do grafo tiverem pesos, bij pode conter, no lugar de 1, o peso (custo) dessa mesma aresta. Na figura a seguir temos um grafo dirigido. Note que as arestas contêm sentido duplo e essa informação foi apresentada na matriz de adjacência. Figura 15 Matriz de adjacência al ri/ Sh ut te rs to ck A seguir, construiremos a matriz de adjacência conhecendo o grafo que a representa. Para saber mais sobre essa importante afirmação de Euler que se tornou o primeiro teorema da teo- ria dos grafos, sugerimos a obra Grafos: conceitos, algoritmos e aplicações, de Marco Cesar Goldbarg e Elizabeth Goldbarg. O teorema está descrito na página 89 da obra. GOLDBARG, M.; GOLDBARG, E. 1. ed. Rio de Janeiro: Elsevier, 2012. Já na obra Fundamentos de teoria dos grafos para computação, de Maria do Carmo Nicoletti e Estevam R. Hruschka Júnior, página 163, também é possível acompanhar o teorema e sua prova. Os autores apresentam exemplos que nos auxiliam a fixar a ideia e visualizar diferen- tes situações aplicadas ao teorema. NICOLETTI, M. C.; HRUSCHKA JÚNIOR, E. R. 3. ed. Rio de Janeiro: LTC, 2018. Livro Grafos e árvores 135 Exemρlo 3 Analise o grafo a seguir (Figura 16) e escreva a matriz de adjacência dele. Figura 16 Grafo não dirigido a4 a1 a2 a3 a5 v1 v3 v4 v2 v5 Fonte: Elaborada pela autora. A matriz de adjacência apresenta a conexão entre os vértices. Assim, teremos: 0 1 0 0 1 0 0 0 0 1 0 1 0 1 1 1 1 1 0 0 0 0 1 0 0 � � � � � �� � � � � � � � � v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 B = Quando trabalhamos com grafos direcionados, podemos adotar a chamada matriz de incidência. Assim, usa-se o sinal positivo ou negativo em relação aos vértices e às suas arestas incidentes, deixando evidente o vértice de chegada ou de partida. Com isso, se desejamos representar matricialmente um grafo G com n vértices e m arestas, podemos escrever uma matriz Bn⨯m da forma: B i j se a aresta j sai do vértice i se( , ) , ,� �1 1 a arresta j chega no vértice i 0, caso contrário � � � �� Para compreender mais sobre a matriz de adjacên- cia, sugerimos assistir ao vídeo Algoritmos e Estrutu- ras de Dados - USP - Matriz de Adjacência em Grafos. Disponível em: https://youtu.be/ q3lh8NcmH14. Acesso em: 24 ago. 2021. Vídeo https://youtu.be/q3lh8NcmH14 https://youtu.be/q3lh8NcmH14 136 Matemática para Computação Esse conceito pode ser observado por meio do digrafo apresentado na Figura 17. Note que a matriz de incidência foi montada respeitando as relações entre arestas direcionadas e nós. B i j a a a ( , ) � � � � � � � � � � � � � � 1 2 3 1 0 1 1 1 0 0 1 1 1 2 3 Figura 17 Digrafo com três vértices e três arestas a1 a2 a3 1 2 3 Fonte: Elaborada pela autora. Além da representação matricial, podemos representar os grafos por intermédio de listas. Na computação, chamamos de listas as estru- turas de dados que permitem armazenar informações de determinadotipo em uma ordem previamente especificada. Uma lista pode armaze- nar, por exemplo, informações dos vértices ou das arestas. A implementação das listas pode ser feita por meio de arrays ou encadeamentos. Uma matriz é um array multidimensional. Já um vetor é um array unidimensional. Cada elemento de um array deve ser colocado em uma posição es- pecífica e, caso seja necessário retirar algum elemento dele, pode ha- ver a necessidade de reposicionamento dos elementos restantes. Já o encadeamento envolve conceitos de programação, como pon- teiros e referências. Para criar listas encadeadas, é preciso que os elementos da lista referenciem algum outro elemento, ou seja, indiquem onde podemos encontrar um outro elemento. As listas de adjacência, as quais vere- mos na sequência, são listas encadeadas, pois têm os vértices fazendo referência a outros vértices conectados a eles. Vamos entender esse conceito como mais uma proposta de repre- sentação computacional dos grafos. Grafos e árvores 137 5.2.2 Representação por meio de lista de adjacências Uma lista de adjacência em um grafo será composta por todos os vértices nos quais existe uma aresta como conexão. Nesse caso, essa será a lista de adjacência desse vértice. Considere o grafo representado na Figura 18 a seguir. Figura 18 Grafo não dirigido de cinco nós e cinco arestas Fonte: Elaborada pela autora. a4 a1 a2 a3 a5 v1 v3 v4 v2 v5 Teremos as seguintes listas vinculadas aos vértices v1, v2, v3, v4 e v5, respectivamente: • Adj[v1] = [v2,v4]; • Adj[v2] = [v1,v4]; • Adj[v3] = [v4,v5]; • Adj[v4] = [v1,v2,v3]; • Adj[v5] = [v3]. Em um grafo dirigido, o princípio será o mesmo. Assim, seja o grafo a seguir (Figura 19), montaremos as listas de adjacência refe- rentes a cada vértice. 138 Matemática para Computação Figura 19 Digrafo de 3 vértices Fonte: Elaborada pela autora. a1 a2 a3 v2 v1 v3 Esse grafo será representado pelas seguintes listas de adjacência: • Adj[v1] = [ ]; • Adj[v2] = [v1]; • Adj[v3] = [v1, v2]. Note que as listas de adjacência de cada vértice respeitam o sen- tido da aresta. Portanto, é possível escolher por representações computacionais distintas. Essa escolha levará em consideração: características especí- ficas da aplicação, seleção da linguagem de programação, necessidade de representação visual, dentre outras características. 5.3 Conceito de árvore Vídeo Talvez o exemplo mais simples que nos permita entender o conceito de árvore seja a árvore genealógica (Figura 20). Iv an A le x Bu rc ha k/ Sh ut te rs to ck Figura 20 Árvore genealógica Grafos e árvores 139 Isso mesmo, a árvore genealógica que estudamos desde a educação infantil, a qual construímos diversas vezes em sala de aula e permite entendermos nossa ancestralidade, é um grafo com características dis- tintas que possibilita que a nomeemos de árvore. Matematicamente, uma árvore é um grafo conexo sem ciclos. Com o desenvolvimento da teoria dos grafos, muitas áreas benefi- ciaram-se de suas definições, para que pudessem ser estruturadas e melhor explicadas conceitualmente. Gustav Robert Kirchhoff, nascido em Königsberg (1824-1877), exa- tamente onde toda a teoria dos grafos começou, utilizou-a para de- senvolver e validar seu trabalho com circuitos elétricos, tendo como particular conceito nessa construção as árvores. Esses resultados serviram de incentivo para que outros pesquisa- dores e cientistas, das mais diversas áreas, utilizassem esses conceitos em seus trabalhos. Como vimos, uma lista encadeada é uma estrutura de dados linear. Nela, os elementos do conjunto são associados por relações de “poste- rior” ou “anterior”, na intenção de criar uma espécie de fileira imaginária. As árvores são estruturas de dados não lineares, nas quais os ele- mentos costumam ser associados por relações de “esquerdo”, “direito”, “inferior”, “superior”, “pai”, “filho”, “menor”, “maior” etc. Essas estrutu- ras formam grafos conexos e acíclicos. Quando representados gra- Aa ar gl ~c om m on sw ik i/W ik im ed ia C om m on s Gustav Robert Kirchhoff Figura 21 Tipos de árvores de decisão Ze rn L ie w/ Sh ut te rs to ck O material de aula do professor José Augusto Baranauskas, do depar- tamento de ciência da computação e matemática da Universidade de São Paulo, apresenta conceitos, exercícios e aplicações computacionais sobre gra- fos e árvores. Os exemplos são bastante didáticos e os exercícios auxiliam na melhor compreensão do tema estudado. Disponível em: http://dcm.ffclrp. usp.br/~augusto/teaching/aedii/ AED-II-Grafos.pdf. Acesso em: 24 ago. 2021. Saiba mais ficamente, formam diagramas que remetem à estrutura física de uma árvore (da natureza), com galhos ramificados. De acordo com Almeida (2018, p. 19), “como nem todo grafo é uma árvore, podemos afirmar que um grafo será uma árvore se e somente se existir um único ca- minho entre dois vértices quais- quer deste grafo”. Todo grafo conexo tem, ao menos, uma árvo- re composta de todos seus vérti- ces e algumas de suas arestas. http://dcm.ffclrp.usp.br/~augusto/teaching/aedii/AED-II-Grafos.pdf http://dcm.ffclrp.usp.br/~augusto/teaching/aedii/AED-II-Grafos.pdf http://dcm.ffclrp.usp.br/~augusto/teaching/aedii/AED-II-Grafos.pdf 140 Matemática para Computação Vamos entender esse princípio: considere o grafo apresentado na Figura 22. Figura 22 Conceito de árvore geradora Fonte: Elaborada pela autora. a1 a4 a5 a6 a2 a3 v2 v5v6 v4 v1 v3 Observe que se retirarmos a aresta a3, ainda assim todos os vértices estarão interligados. Com isso, se os vértices são, por exemplo, pontos de entregas de produtos e queremos analisar qual o caminho mínimo para passarmos por todos esses pontos, precisaremos que eles este- jam conectados, mas não necessariamente usaremos todas as arestas como vias de acesso aos pontos de entrega. Nesse momento entramos em um conceito chamado caminho míni- mo, que explicaremos melhor na sequência. Mas, independentemente de sabermos qual seria o trajeto mais curto, precisamos encontrar todas as árvores possíveis presentes nesse grafo, ou seja, todas as formas de chegarmos a todos os vértices sem que exista dualidade entre os caminhos. Esse tipo de problema é conhecido como problema de roteamento. As três figuras a seguir apresentam as árvores geradoras para o gra- fo apresentado na Figura 22, observe. Figura 23 Primeiro exemplo de árvore geradora Fonte: Elaborada pela autora. a1 a4 a5 a6 a2 v2 v5v6 v4 v1 v3 Grafos e árvores 141 Figura 24 Segundo exemplo de árvore geradora Fonte: Elaborada pela autora. a4 a5 a6 a2 a3 v2 v6 v4 v1 v5 v3 Figura 25 Terceiro exemplo de árvore geradora Fonte: Elaborada pela autora. a5 a1 a6 a2 a3 v2 v6 v4 v1 v5 v3 Em qualquer uma das três árvores temos todos os pontos de entrega interconectados. Com isso, podemos começar a pensar em qual dessas três árvores geradoras temos um conjunto de rotas que minimiza a dis- tância para as entregas, ou seja, qual é a árvore geradora mínima. Note que, nesse caso, é necessário conhecermos o valor das arestas ou a função aplicada em cada um desses caminhos, que pode levar em consideração a distância, o custo do combustível, o tipo de meio de locomoção usado etc. Portanto, para esse fim, precisamos de um grafo com pesos. Observe a definição a seguir. Definição 3 Uma árvore geradora mínima, para um grafo com pesos, é uma árvore geradora que tem o menor peso total possível dentre todas as possíveis árvores gerado- ras do grafo. 142 Matemática para Computação Note que dependendo da quantidade de vértices e arestas de um grafo, o número de árvores geradoras pode ser enorme. Por exemplo, o grafo de Petersen, que pode ser analisado na Figura 26 a seguir, tem 2.000 árvores geradoras. Figura 26 Grafo de Petersen Le sh ab iru ko v/ W ik im ed ia C om m on s Existem alguns algoritmos conhecidos para se obter uma árvore geradora mínima. Desses, o algoritmo de Kruskal(1956) e algoritmo de Prim (1957) talvez sejam os mais populares. Ambos são chamados de algoritmos gulosos, pois fazem escolhas levando em consideração a melhor solução imediata (mais próxima). Com os algoritmos de busca aplicados aos grafos e, particularmen- te, às árvores, notamos um campo imenso de aplicações possíveis que vai muito além dos denominados problemas de roteamento. Na sequência, vamos ver mais alguns conceitos importantes sobre árvores que podem ser aplicados a procedimentos de busca. 5.4 Raízes e árvores binárias Vídeo Como foi mencionado nas seções anteriores, uma árvore é um gra- fo conexo e acíclico. Na formação de uma árvore, podemos destacar al- guns pontos importantes, sendo um deles o conceito de raiz da árvore. Uma árvore que apresenta um vértice distinto facilmente distinguí- vel é chamada árvore enraizada (Figura 27). Esse vértice é considerado o vértice raiz. Nesse caso, afirmamos que os vértices têm hierarquia. Assista aos vídeos Algo- ritmo de Kruskal - Árvore Geradora Mínima e Algo- ritmo de Prim – Teoria dos Grafos (Exemplo Prático). Disponível em: https://www.youtube. com/watch?v=3Q6RdxGmDgQ. Acesso em: 24 ago. 2021. Disponível em: https://www. youtube.com/watch?v=Pgf- AL1vYb4. Acesso em: 24 ago. 2021. Vídeo Os algoritmos de Kruskal e de Prim podem ser encontrados em diversas obras específicas sobre grafos. Sugerimos a obra Grafos: introdução e práti- ca, de Boaventura Netto e Jurkiewicz, p. 86 (Kruskal) e p. 87 (Prim). BOAVENTURA NETTO, P. O; JURKIEWICZ, S. 2. ed. São Paulo: Blücher, 2017. Saiba mais https://www.youtube.com/watch?v=3Q6RdxGmDgQ. Acesso em: 24 ago. 2021. Disponível em: https://www.youtube.com/watch?v=Pgf-AL1vYb4 https://www.youtube.com/watch?v=3Q6RdxGmDgQ. Acesso em: 24 ago. 2021. Disponível em: https://www.youtube.com/watch?v=Pgf-AL1vYb4 https://www.youtube.com/watch?v=3Q6RdxGmDgQ. Acesso em: 24 ago. 2021. Disponível em: https://www.youtube.com/watch?v=Pgf-AL1vYb4 https://www.youtube.com/watch?v=3Q6RdxGmDgQ. Acesso em: 24 ago. 2021. Disponível em: https://www.youtube.com/watch?v=Pgf-AL1vYb4 https://www.youtube.com/watch?v=3Q6RdxGmDgQ. Acesso em: 24 ago. 2021. Disponível em: https://www.youtube.com/watch?v=Pgf-AL1vYb4 https://www.youtube.com/watch?v=3Q6RdxGmDgQ. Acesso em: 24 ago. 2021. Disponível em: https://www.youtube.com/watch?v=Pgf-AL1vYb4 Grafos e árvores 143 Podemos montar uma árvore genealógica como uma árvore enrai- zada. Para isso, escolhemos um dos membros para o primeiro casal e partimos dali para seus filhos e assim sucessivamente. Figura 27 Árvore enraizada to vo va n/ Sh ut te rs to ck É visível a identificação da raiz de uma árvore, e sua localização é mui- tas vezes considerada o ponto de partida para algoritmos de busca para esse tipo de árvore. Uma árvore não enraizada é uma árvore dita livre. Nicoletti e Hruschka Júnior (2018, p. 184) trazem a seguinte definição para árvore binária: “é um grafo vazio ou tem um vértice especial r chama- do raiz, e os demais vértices da árvore são subdivididos em dois subcon- juntos disjuntos: as subárvores esquerda e direita de r, as quais são também árvores binárias”. A Figura 28 exemplifica tipos dessas árvores. Figura 28 Tipos de árvores binárias Sh ad eD es ig n/ Sh ut te rs to ck Árvore equilibrada ou árvore binária cheia Árvore em profundidade Árvore em largura 144 Matemática para Computação Uma árvore binária pode ser dita completa ou incompleta. A seguir temos a definição de árvore binária completa. Definição 4 Uma árvore binária completa é uma árvore enraizada, tal que existe exatamente um vértice de grau dois e cada um dos vértices restantes tem grau um ou três. Naturalmente, o vértice de grau dois é o vértice raiz da árvore. Caso a definição não se verifique, temos uma árvore binária incompleta. Uma aplicação envolvendo árvores binárias pode ser encontrada em trabalhos sobre otimização e distribuição de sinal em redes. Tam- bém existem aplicações na área de redes óticas e otimização de siste- mas submersos para gerenciamento de extração de petróleo 1 . Algumas propriedades das árvores binárias permitem que possa- mos estimar o número de operações, vértices e arestas envolvidas na solução de um algoritmo de busca. Vamos conhecê-las a seguir. 5.4.1 Propriedades de árvores binárias As árvores binárias costumam ser usadas em diversas aplicações por sua característica essencial, a qual é a de permitir que seja tomada a decisão entre dois caminhos (direita ou esquerda) até que se chegue a um objetivo determinado. Assim, para chegarmos ao objetivo com rapidez e eficiência, é essencial entendermos algumas propriedades e operações que permitem calcular o número de vértices e arestas e compreendermos operações usadas em um algoritmo de busca que tem como base uma árvore binária. O número de vértices em uma árvore binária completa (com três ou mais vértices) é sempre ímpar. Já uma árvore binária comple- ta com n vértices terá p n� �1 2 vértices pendentes, que são o objetivo da busca. A altura h de uma árvore binária é a distância entre a raiz e seu descendente 2 mais afastado. Se T é uma árvore binária completa composta por p vértices pen- dentes e tem altura h, então: Alguns desses exemplos podem ser observados no livro de Nicoletti e Hruschka Júnior (2018). 1 Um descendente em uma árvore binária é qualquer vértice (nó) que possa ser atingido por meio da decisão entre os dois caminhos possíveis (direita ou esquerda) em qualquer ordem. 2 Grafos e árvores 145 I. p ≤ 2h II. h p l n� � � �|log | | og |2 2 1 2 1 Conhecendo a estrutura dos grafos, suas designações e proprieda- des, trazemos, a seguir, a interpretação do conceito de procedimentos de busca. 5.5 Introdução a procedimentos de busca Vídeo Árvore binárias e árvores geradoras mínimas são muito utilizadas em procedimentos de busca. Isso ocorre, pois esse tipo de grafo é co- mumente aplicado em testes que apresentam duas possíveis respostas. Tendo como ponto de partida a raiz da árvore, o teste é iniciado e nos encaminha para um dos dois vértices da próxima camada (nível) em que novos testes são efetuados. Quando atingimos o objetivo da busca (vértice pendente), o proce- dimento de busca se encerra. Com isso, entender os procedimentos de busca depende da definição do conceito de distância entre vértices (nós). Tendo em um grafo os vértices u e v, sendo u o vértice inicial e v o vértice final, calcular a distância ou o comprimento do caminho entre esses dois vértices depende de algumas propriedades algébricas, como: I. d(u, v) ≥ 0 e d(u, v) = 0 se, e somente se, u = v. II. d(u, v) = d(v, u) – comutatividade. III. d(u, v) + d(v, w) ≥ d(u, w) – desigualdade triangular. O grafo da Figura 29 representa graficamente a distância medindo uma unidade de medida em cada aresta. Figura 29 Distância 1 em cada aresta Fonte: Elaborada pela autora. 1 1 1 1 v1 v2 v4 v3 146 Matemática para Computação A matriz de distâncias tem como elementos a distância entre os vér- tices que a compõem. Observe a seguir a matriz de distância Dist(G) referente ao grafo da Figura 29. Dist G( ) � 1 2 1 0 1 0 1 2 2 1 0 1 1 2 1 2 � � � � � � � � � � � � v1 v2 v3 v4 v1 v2 v3 v4 Note que a matriz de distância é construída para a menor distância entre dois vértices. Nos procedimentos de busca mais conhecidos estão os chamados: procedimentos de busca em profundidade (depth first) e os procedimentos de busca em largura (breadth first) A busca em profundidade é um algoritmo que caminha pelo grafo bus- cando, sempre que possível, o descendente mais distante (o mais profundo). A estratégia desse tipo de busca é, com base em um vértice v recém-descoberto, explorar as arestas que partem de v que ainda não foram exploradas. Quando todas as arestas adjacentes a v forem visitadas, a busca come- ça a explorar os vértices para trás, tais que estes saiamdo vértice v já descoberto. O algoritmo é a base para muitos outros algoritmos importantes, tais como: a verificação de grafos acíclicos, a ordenação topológica e os componentes fortemente conectados. Já a busca em largura visa encontrar o comprimento de um cami- nho entre um vértice e seu descendente mais distante, usando o me- nor número de arestas. De acordo com Goldbarg e Goldbarg (2012, p. 65), a busca em largura pode ser definida como: “uma busca é denominada em largura se, para o critério de seleção de vértices, for exigido que a escolha seja feita sobre o vértice não marcado menos recentemente alcançado na busca”. Com essas duas estratégias de busca determinadas, podemos apresentar alguns dos algoritmos mais conhecidos que as utilizam e que permitem calcular o caminho mínimo para a obtenção de um vértice pendente. Conheceremos alguns desses algoritmos a seguir. Para conhecer um pouco mais sobre os algoritmos de busca, sugerimos a leitura do material Algorit- mos em grafos, elaborado por Charles Ornelas Almeida, Israel Guerra e Nivio Ziviani. Disponível em: http://www2.dcc. ufmg.br/livros/algoritmos/cap7/ slides/pascal/completo1/cap7.pdf. Acesso em: 24 ago. 2021. Leitura http://www2.dcc.ufmg.br/livros/algoritmos/cap7/slides/pascal/completo1/cap7.pdf http://www2.dcc.ufmg.br/livros/algoritmos/cap7/slides/pascal/completo1/cap7.pdf http://www2.dcc.ufmg.br/livros/algoritmos/cap7/slides/pascal/completo1/cap7.pdf Grafos e árvores 147 5.5.1 Algoritmos de caminho mínimo A teoria dos grafos é largamente utilizada em problemas de rotea- mento, sendo, nesses casos, usados os chamados algoritmos de busca. Dentre os algoritmos mais conhecidos, encontram-se o algoritmo do vizinho mais próximo, o algoritmo de Dijkstra, o algoritmo de Floyd etc. O algoritmo de Dijkstra tem como conceito base a construção de uma matriz de distâncias, a qual terá seus elementos sendo a menor distância entre dois vértices. O cientista da computação holandês, Edsger Wybe Dijkstra, nasceu em Roterdã, 1930, e faleceu em Nuenen. Ele fez diversas contribuições nas áreas de desenvolvimento de algoritmos, sistemas operacionais e processamento distribuído. Em 1972, recebeu o prêmio Turing por suas contribuições no desenvolvimento de linguagens de programação. O conjunto S que será construído com base no algoritmo Dijkstra é composto por vértices cujos caminhos mais curtos até um vértice origem já são conhecidos. Esse conjunto produz uma árvore de caminhos mais curtos de um vértice origem s para todos os vértices que são alcançáveis a partir de s. Não vamos nos aprofundar na estrutura desses algoritmos, pois, como comentamos no início do capítulo, a teoria dos grafos é bastante extensa, riquíssima e existem obras específicas sobre o tema. Mas caso tenha curiosidade para conhecer e até implementar esses algoritmos, sugerimos alguns materiais. O Problema do Caixeiro-viajante (PCV) é do tipo “caminho mínimo”. Seu algoritmo é estruturado para que seja possível visitar, em ordem sequencial, um conjunto de pontos dispersos de um grafo, ou seja, sair de um vértice inicial, visitar todos os outros e voltar para a origem inicial sem repetir nenhum vértice. Podemos indicar muitas aplicações que usam o PCV. Dentre elas, escolhemos o artigo publicado pela Associação Brasileira de Engenharia de Produção (ABREPO), intitulado Teoria dos grafos aplicada à roteirização na logística de distribuição: o problema do caixeiro viajante em uma empresa fabricante de farinha de trigo. Acesso em: 24 ago. 2021. http://www.abepro.org.br/biblioteca/TN_STO_291_1644_39148.pdf Artigo Assim, vimos a estrutura de um grafo e suas ramificações. Conhe- cemos as terminologias do tema, alguns tipos de grafos e formas de representação computacional, que nos deram uma base importante e que conecta a matemática e a computação de maneira aplicada. Assista aos dois vídeos sobre os algoritmos de Floyd e Dijkstra, Algoritmo de Floyd e Algoritmo de Dijkstra. Escolha uma linguagem de progra- mação de seu domínio e reflita sobre as possibili- dades de implementação computacional de um ou mais algoritmos de busca nessa linguagem. Disponível em: https://youtu.be/Dfga- Bkp02HY. Acesso em: 24 ago. 2021. Disponível em: https://youtu.be/vzW- VCqYDlAs. Acesso em: 24 ago. 2021. Vídeo Ha m ilt on R ic ha rd s/ W ik im ed ia C om m on s Edsger Wybe Dijkstra https://pt.wikipedia.org/wiki/Roterd%C3%A3 https://pt.wikipedia.org/wiki/1930 https://pt.wikipedia.org/wiki/Nuenen https://youtu.be/DfgaBkp02HY https://youtu.be/DfgaBkp02HY https://youtu.be/vzWVCqYDlAs https://youtu.be/vzWVCqYDlAs 148 Matemática para Computação CONSIDERAÇÕES FINAIS Fechamos o capítulo destinado à teoria dos grafos e árvores e espera- mos que, após esta introdução, você esteja curioso para aprender ainda mais sobre esse tema tão rico e aplicável em nosso cotidiano e em outras áreas do conhecimento. Podemos até afirmar que as relações sociais por meios digitais não existiriam sem a teoria dos grafos e que nossa comida chegaria gelada caso o entregador de pizza não otimizasse sua rota de entrega. Percebemos que muito dessa teoria é aplicada mesmo sem notarmos sua existência ou importância. Mas agora que você conhece um pouco so- bre ela, poderá enxergar a matemática por trás de tarefas simples e com- plexas, por exemplo, as conexões neurais realizadas pelo nosso cérebro. Sim, elas também podem ser representadas por grafos. Indicamos que acesse os materiais sugeridos como complementação do conteúdo. Acreditamos que o tripé teoria, prática e aplicação é ne- cessário para a boa compreensão de qualquer conceito. ATIVIDADES Construa uma matriz de adjacência e uma matriz de incidência para o grafo apresentado a seguir e descreva as diferenças entre os dois resul- tados. Note que a1 = [v4, v1], a2 = [v5, v2], a3 = [v1, v3], a4 = [v2, v4] e a5 = [v3, v5]. v1 v5 a1 a2 a3 a5 a4 v2 v4 v3 Atividade 1 Grafos e árvores 149 Seja o grafo exposto na figura a seguir. v1 v6 v5 v2 v4 v3 Apresente uma árvore geradora para esse grafo usando o conceito de extração de arestas. Atividade 2 Usando as árvores binárias, desenvolva um grafo para representar a quantidade de jogos necessários em um torneio de vôlei com 16 inscritos. Atividade 3 REFERÊNCIAS ALMEIDA, L. de A. e. Árvores: algoritmos e aplicações. 2018. Dissertação (Mestrado em Matemática) – Instituto de Matemática Pura e Aplicada, Rio de Janeiro. Disponível em: https://impa.br/wp-content/uploads/2018/03/TCC_2018_Lauro-e-Almeida.pdf. Acesso em: 23 ago. 2021. BOAVENTURA NETTO, P. O; JURKIEWICZ, S. Grafos: Introdução e prática. São Paulo: Blücher, 2017. FLOYD, T. L. Sistemas digitais: fundamentos e aplicações. Porto Alegre: Bookman, 2007. GOLDBARG, M.; GOLDBARG, E. Grafos: conceitos, algoritmos e aplicações. Rio de Janeiro: Elsevier, 2012. GOOGLE EARTH. 2021. Disponível em: https://earth.google.com/web/search/Kalinin- grad,+Oblast+de+Kaliningrado,+R%c3%bassia/@54.6947304,20.56456713,4.1195937 9a,6991.5150592d,35y,0h,0t,0r/data=CpcBGm0SZwolMHg0NmUzM2Q4ZDRiN2MyM- WE5OjB4NTA1MDk2MDAxNjEyNmVkMxmFG5VA71pLQCG_x6pSxHM0QCosS2FsaW5pb- mdyYWQsIE9ibGFzdCBkZSBLYWxpbmluZ3JhZG8sIFLDunNzaWEYASABIiYKJAm582YmF0Q- 3wBHfS-j8FUg3wBnqs6-zuJxHwCGsWQUE7aBHwA. Acesso em: 23 ago. 2021. NICOLETTI, M. C.; HRUSCHKA JÚNIOR, E. R. Fundamentos da teoria dos grafos para computação. Rio de Janeiro: LTC, 2018. https://earth.google.com/web/search/Kaliningrad,+Oblast+de+Kaliningrado,+R%c3%bassia/@54.6947304,20.56456713,4.11959379a,6991.5150592d,35y,0h,0t,0r/data=CpcBGm0SZwolMHg0NmUzM2Q4ZDRiN2MyMWE5OjB4NTA1MDk2MDAxNjEyNmVkMxmFG5VA71pLQCG_x6pSxHM0QCosS2FsaW5pbmdyYWQsIE9ibGFzdCBkZSBLYWxpbmluZ3JhZG8sIFLDunNzaWEYASABIiYKJAm582YmF0Q3wBHfS-j8FUg3wBnqs6-zuJxHwCGsWQUE7aBHwA https://earth.google.com/web/search/Kaliningrad,+Oblast+de+Kaliningrado,+R%c3%bassia/@54.6947304,20.56456713,4.11959379a,6991.5150592d,35y,0h,0t,0r/data=CpcBGm0SZwolMHg0NmUzM2Q4ZDRiN2MyMWE5OjB4NTA1MDk2MDAxNjEyNmVkMxmFG5VA71pLQCG_x6pSxHM0QCosS2FsaW5pbmdyYWQsIE9ibGFzdCBkZSBLYWxpbmluZ3JhZG8sIFLDunNzaWEYASABIiYKJAm582YmF0Q3wBHfS-j8FUg3wBnqs6-zuJxHwCGsWQUE7aBHwAhttps://earth.google.com/web/search/Kaliningrad,+Oblast+de+Kaliningrado,+R%c3%bassia/@54.6947304,20.56456713,4.11959379a,6991.5150592d,35y,0h,0t,0r/data=CpcBGm0SZwolMHg0NmUzM2Q4ZDRiN2MyMWE5OjB4NTA1MDk2MDAxNjEyNmVkMxmFG5VA71pLQCG_x6pSxHM0QCosS2FsaW5pbmdyYWQsIE9ibGFzdCBkZSBLYWxpbmluZ3JhZG8sIFLDunNzaWEYASABIiYKJAm582YmF0Q3wBHfS-j8FUg3wBnqs6-zuJxHwCGsWQUE7aBHwA https://earth.google.com/web/search/Kaliningrad,+Oblast+de+Kaliningrado,+R%c3%bassia/@54.6947304,20.56456713,4.11959379a,6991.5150592d,35y,0h,0t,0r/data=CpcBGm0SZwolMHg0NmUzM2Q4ZDRiN2MyMWE5OjB4NTA1MDk2MDAxNjEyNmVkMxmFG5VA71pLQCG_x6pSxHM0QCosS2FsaW5pbmdyYWQsIE9ibGFzdCBkZSBLYWxpbmluZ3JhZG8sIFLDunNzaWEYASABIiYKJAm582YmF0Q3wBHfS-j8FUg3wBnqs6-zuJxHwCGsWQUE7aBHwA https://earth.google.com/web/search/Kaliningrad,+Oblast+de+Kaliningrado,+R%c3%bassia/@54.6947304,20.56456713,4.11959379a,6991.5150592d,35y,0h,0t,0r/data=CpcBGm0SZwolMHg0NmUzM2Q4ZDRiN2MyMWE5OjB4NTA1MDk2MDAxNjEyNmVkMxmFG5VA71pLQCG_x6pSxHM0QCosS2FsaW5pbmdyYWQsIE9ibGFzdCBkZSBLYWxpbmluZ3JhZG8sIFLDunNzaWEYASABIiYKJAm582YmF0Q3wBHfS-j8FUg3wBnqs6-zuJxHwCGsWQUE7aBHwA https://earth.google.com/web/search/Kaliningrad,+Oblast+de+Kaliningrado,+R%c3%bassia/@54.6947304,20.56456713,4.11959379a,6991.5150592d,35y,0h,0t,0r/data=CpcBGm0SZwolMHg0NmUzM2Q4ZDRiN2MyMWE5OjB4NTA1MDk2MDAxNjEyNmVkMxmFG5VA71pLQCG_x6pSxHM0QCosS2FsaW5pbmdyYWQsIE9ibGFzdCBkZSBLYWxpbmluZ3JhZG8sIFLDunNzaWEYASABIiYKJAm582YmF0Q3wBHfS-j8FUg3wBnqs6-zuJxHwCGsWQUE7aBHwA 150 Matemática para Computação Resolução das atividades 1 Por que estudar matemática? 1. Sabendo que um algoritmo é compreendido como um processo que mostra detalhadamente os métodos necessários para a resolução de uma atividade, e que podemos pensar nessa estrutura em formato de pseudocódigo como estrutura inicial, descreva um pseudocódigo para o cálculo da expressão numérica 1 + 3(5 + 1). Início: Sejam os números 1, 3 e 5 dispostos como 1 + 3(5 + 1), então: Resolva a operação dentro dos parênteses. Se encontrar multiplicação ou divisão, resolva. Caso contrário, resolva a adição ou a subtração. Após eliminar os parênteses, resolva. Se encontrar multiplicação ou divisão, resolva. Caso contrário, resolva a adição ou a subtração. Finalize imprimindo o resultado da expressão. Fim. 2. Descreva o modelo matemático que pode ser utilizado para representar a definição do problema a , para a > 0, usando apenas as quatro operações aritméticas. Conseguimos transformar o problema real dado por a , com a > 0 usando a expressão x a= x2 = a Logo, f(x) = x2 – a Assim, determinando a raiz de f(x), que se transformará em uma equação do segundo grau da forma x2 – a = 0 percebemos que essas raízes serão a e − a� . Resolução das atividades 151 3. Uma pesquisa foi realizada coletando dados referentes à altura de alunos de uma sala de aula. Esse tipo de dado é qualitativo ou quantitativo? Justifique. A altura coletada de um grupo de pessoas é um dado quantitativo. Esse tipo de dado pode ser classificado por meio de relações numéricas de intervalos de classe por se tratar de um dado numérico que não pode ser representado por um número inteiro, havendo a necessidade de ser representado por um decimal, que pode assumir qualquer valor após a vírgula, por exemplo, 152,1 cm. É também chamado de dado quantitativo contínuo. 2 Noções sobre sistemas de numeração 1. Podemos considerar o sistema de numeração romano um sistema aditivo ou um sistema posicional? Explique. O sistema de numeração romano, usado em algumas representações até hoje, como em relógios e para marcar itens, é um sistema aditivo, e podemos perceber essa dinâmica, por exemplo, quando precisamos escrever números como 20 (XX) e 30 (XXX), conforme é apresentado na figura a seguir. im ag es to ck de si gn /S hu tte rs to ck Números Romanos Ele é um típico sistema de numeração aditivo, mas que teve alguns avanços quando comparado a sistemas desse tipo que não permitiam a escrita rápida de números muito grandes. 2. É possível converter um número na base 10 para a base hexadecimal por meio de divisões sucessivas? Explique essa conversão e converta o número (9)10 para essa base. 152 Matemática para Computação Como a base hexadecimal é composta de um número de algarismos maior do que a base 10, qualquer número menor que 10 não precisa ser convertido, sendo escrito diretamente na sua forma decimal e apenas corrigindo a base. Assim, para o número (9)10 teremos (9)10 = (9)16. Contudo, se esse número fosse maior do que 9, por exemplo, se tivéssemos (10)10, teríamos como conversão (10)10 = (A)16. Por meio da divisão, precisamos fazer 10 ÷ 16 = 0 → Resto 10. Nesse caso, precisamos compreender quem é o representante para 10 na base hexadecimal, e esse elemento é a letra A, portanto (A)16 = (10)10. 3. Considere a escrita do número de Napier da forma e = 2,718... e e n n � � � � � �� � � 0 1 1 0 1 1 1 2 1 3 � ! ! ! ! ! No primeiro caso, devemos usar qual tipo de ajuste numérico para obter um número finito? E no segundo caso? Quais são os erros envolvidos em cada um dos casos? Ao escrever o número de Napier da forma e = 2,718 ..., precisamos fazer um arredondamento para obter um número finito. Nesse caso, teríamos o valor e ≈ 2,72, que acarretará um erro de arredondamento. Quanto ao segundo caso: e n n � � � � � �� � � 0 1 1 0 1 1 1 2 1 3 � ! ! ! ! ! Como temos uma série numérica, podemos transformar e para uma forma finita por meio de um truncamento nos termos da série. Portanto, teremos um típico erro de truncamento. 3 Matrizes 1. Nas regras do xadrez, cada peça tem uma movimentação possível. Por exemplo, o cavalo só pode se movimentar em “L”, ou seja, • duas casas para a direita (ou para a esquerda) e uma para frente (ou para trás); • uma casa para a direita (ou para a esquerda) e duas casas para frente (ou para trás). Resolução das atividades 153 A figura a seguir é um exemplo das possíveis movimentações que um cavalo na casa 4D pode fazer. 8 7 6 5 4 3 2 1 HGFEDCBA Explique, usando a notação “linha-coluna”, as possíveis movimentações do cavalo branco que está na casa 1G (observação: ele não pode ficar sobre outra peça branca). Sabendo das possíveis movimentações do cavalo e assumindo que o cavalo branco, que precisa ser movimentado, está na posição 1G, conforme a figura, temos que este poderia se mover para as casas 3F ou 3H. Va pa rt/ Sh ut te rs to ck 154 Matemática para Computação 2. De acordo com o conceito de base para um espaço de vetores, indique dois conjuntos de vetores que formam uma base para o ℝ³. Justifique o porquê dessas escolhas. Podemos escolher muitos conjuntos com a característica de serem base para ℝ³. Todos eles precisam respeitar dois conceitos: • serem formados por vetores LI; • gerarem ℝ³. Assim, respeitando esses parâmetros, definimos: • o conjunto de vetores canônicos V = {e1, e2, e3}, em que e1 = (1, 0, 0), e2 = (0, 1, 0) e e3 = (0, 0, 1); • W = {v1, v2, v3}, em que v1 = (1, 2, 3), v2 = (–1, 3, 5) e v3 = (0, 1, 4). Tanto V como W são formados por vetores linearmente independentes. Para verificar essa condição, basta calcular o determinante de ordem 3, composto pelos vetores de cada um desses conjuntos: V �W� � � � � � � 1 0 0 0 1 0 0 0 1 1 0 1 2 3 1 3 5 0 1 4 12 0; Além disso, tanto W como V são conjuntos formados por vetores tridimensionais, sendo, assim, necessários e suficientes para gerarem todo o ℝ³. 3. Explique por que afirmamos que a decomposição LU não é única. Quando realizamos a decomposição LU, obtemos duas matrizes na forma: A a a a a l l l um m mm m mm � � � � � � � � � � � � � � � � � � � � � � 11 1 1 11 1 110� � � � � � � � � � �� � � � � u u L U m mm 1 0 � � � � � � � � � � � � Em geral, a matriz L carrega, na sua diagonal principal, elementos iguais a 1. Contudo, a matriz U, que tem, em sua diagonal principal, elementos que ainda podem ser fatorados, poderia ser escrita com outros tipos de fatoração, pensandona fatoração dos elementos da diagonal principal e carregando esse ajuste para a matriz L. Desse modo, existem diversas maneiras de escrever LU, para obtermos A como resultado. Resolução das atividades 155 4 Sistemas de equações lineares 1. Seja A a matriz dos coeficientes de um sistema de equações lineares do tipo Ax = b, por que precisamos ter det ≠ 0 para garantir a inversão dessa matriz? Explique. De maneira aplicada, resolver um sistema de equações lineares é procurar a intersecção entre as estruturas que o formam. Portanto, precisamos garantir que os vetores que fazem parte desse sistema sejam linearmente independentes. Caso esses vetores sejam linearmente dependentes, precisamos do vetor de termos independentes para garantir algum tipo de solução. Matematicamente a inversa de uma matriz A, quadrada, pode ser calculada pela expressão A det A adj A� � � � � �� � 1 1 Portanto, se det = 0, recairemos em uma divisão que não pode ser realizada, o que inviabiliza o cálculo da inversa de A. 2. Um sistema de equações lineares pode ter como solução infinitas soluções. Isso é válido para o sistema a seguir? Justifique. x y z x y z x y z � � � � � � � � � � � � � � � � 1 2 2 2 2 1 Nesse sistema, rapidamente percebemos que todas as equações que o compõem são equações de planos. Ainda, os coeficientes dessas equações são proporcionais. Assim, se montarmos a matriz ampliada e a escalonarmos, obteremos 1 1 1 1 2 2 2 2 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 � � � � � � � � � � � � � � � � � � � � � � � � ~ | | | Isso significa que pa = pc = 1 e n = 2 > pa, portanto temos um sistema compatível e indeterminado, permitindo-nos concluir que temos infinitas soluções. Nesse caso, teremos geometricamente três planos coincidentes, os quais podem ser observados em: https://www. geogebra.org/3d/uypbwxrt. https://www.geogebra.org/3d/uypbwxrt https://www.geogebra.org/3d/uypbwxrt 156 Matemática para Computação 3. Explique, com suas palavras, o que significa a análise de convergência de um método e qual é a sua importância para garantir o resultado encontrado. Basicamente a análise de convergência é o que nos permite decidir se o método leva a uma solução que se aproxima da solução exata ou não. Os métodos ditos numéricos em geral são descritos por processos iterativos, que, por sua vez, só são válidos se a solução aproximada convergir para a solução exata. Quando analisamos a ordem de convergência e taxa de convergência, já estamos considerando que o método converge (primeira análise a ser verificada). A ordem de convergência e taxa de convergência nos mostrarão como essa solução aproximada converge para a solução real e em qual velocidade. 5 Grafos e árvores 1. Construa uma matriz de adjacência e uma matriz de incidência para o grafo apresentado a seguir e descreva as diferenças entre os dois resultados. Note que a1 = [v4, v1], a2 = [v5, v2], a3 = [v1, v3], a4 = [v2, v4] e a5 = [v3, v5]. v1 v5 a1 a2 a3 a5 a4 v2 v4 v3 Resolução das atividades 157 Como o grafo é direcionado, a adjacência leva em consideração o sentido da aresta. Usando B(i,j)= 1, se i, j A 0, caso contrário �� �� � � �� , teremos a matriz de adjacência da seguinte forma: matriz de adj = 0 1 0 0 0 0 0 0 11 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 � � � � � � � � � � � � � � v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 Para a matriz de incidência usamos: B(i,j)= -1, se a aresta j sai do vértice i 1, se a areesta j chega no vértice i 0, caso contrário � � � �� Portanto, matriz�de�inc v v v v v � � � � � � � � � � 1 2 3 4 5 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 �� � � � � � � � � � � � a a a a a1 2 3 4 5 Note que a matriz de incidência, ao contrário da matriz de adjacência, tem em sua diagonal principal todos os elementos iguais a 1. Isso ocorre porque temos a incidência da aresta 1 sobre o vértice 1 e assim por diante, até o vértice e a aresta 5. Já no caso da matriz de adjacência, a análise é sobre a adjacência entre os vértices. Desse modo, a diagonal principal é formada apenas por elementos nulos, pois um vértice i não exerce influência sobre outro vértice i. Logo, a principal diferença está na questão de que a matriz de adjacência, assim como a lista de adjacência, analisa a adjacência entre vértices. Já a incidência é uma relação entre aresta e vértice. 158 Matemática para Computação 2. Seja o grafo exposto na figura a seguir. v1 v6 v5 v2 v4 v3 Apresente uma árvore geradora para esse grafo usando o conceito de extração de arestas. Podemos descrever algumas árvores geradoras, mas escolhemos a seguinte: v5 v1 v6 v2 v3v4 Note que todos os vértices são acessados por alguma aresta e temos uma árvore geradora mínima. 3. Usando as árvores binárias, desenvolva um grafo para representar a quantidade de jogos necessários em um torneio de vôlei com 16 inscritos. A árvore binária, nesse caso, pode ser dita invertida, pois assumiremos que os vértices pendentes são os 16 times inscritos e os vértices internos mais a raiz, os jogos. Portanto, podemos representá-la como a figura a seguir. Resolução das atividades 159 v1 v3 v5 v7 v9 v11 v13 v15 v2 v4 v6 v8 v10 v12 v14 v16 v17 v18 v19 v20 v21 v22 v23 v24 v25 v26 v27 v28 v29 v30 v31 Então, teremos 16 vértices pendentes, 8 vértices internos na primeira camada, 4 vértices internos na segunda camada e 2 vértices internos na terceira camada. O jogo final é a raiz. Esse cálculo nos permite escrever que, ao todo, temos 31(n) vértices e 30(n – 1) arestas. M A RIN A V A RG A S MARINA VARGAS M A TEM Á TICA PA RA CO M PUTA Çà O M A T E M Á T I C A COMPUTAÇÃO PARA Código Logístico I000122 ISBN 978-65-5821-071-9 9 7 8 6 5 5 8 2 1 0 7 1 9 M A RIN A V A RG A S MARINA VARGAS M A TEM Á TICA PA RA CO M PUTA Çà O M A T E M Á T I C A COMPUTAÇÃO PARA Código Logístico I000122 ISBN 978-65-5821-071-9 9 7 8 6 5 5 8 2 1 0 7 1 9