If you are creating a new XMLDocument from scratch, you may want to start by creating an XmlDeclaration node to add to the node tree. The XmlDocument's CreateXmlDeclaration method provides this functionality.
PERFORMANCE OF XmlDocument SEARCHING
Given that the GetElementsByTagName may search elements at any depth, it is important to design your XML document and search methods carefully. Your XML should be designed so that XML elements with similar names are found at similar depths. Also, the GetElementsByTagName should be called on an XmlElement to prevent searching the whole document. Finally, try to narrow the search area as much as possible by finding the ancestor XmlElement closest to the target elements.
The CreateXmlDeclaration ...